题目描述

字符串 S 包含 n 个字符，字符串的字符从左到右，下标从 1 至 n 。每个字符是 'R' 或 'G' 或 'B' 三者之一。求有多少不同的下标三元组 ( x , y , z )同时满足如下的 3 个条件:

1. 1 <= x < y < z <= N

2. S[x] != S[y] , S[x] != S[z] , S[y] != S[z] ;

3. y - x != z - y

上面的符号 != 表示不相等。

输入格式

第一行，一个整数 n ( 1 <= n <= 4000 )。

第二行，一个字符串 S 。

输出格式

一个整数。

样例

4
RRGB

1

39
RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB

1800

样例解释

样例 1 ： 只有下标三元组 (1,3,4) 满足条件。