题目描述

我们有一个长度为 $N$ 的字符串 $S$，其中包含字符 R、G 和 B。

找到满足以下两个条件的三元组 $(i,~j,~k)~(1 \leq i < j < k \leq N)$ 的数量:

• $S_i \neq S_j$，$S_i \neq S_k$，$S_j \neq S_k$。
• $j - i \neq k - j$。

约束条件

• $1 \leq N \leq 4000$
• $S$ 是一个长度为 $N$ 的字符串，其中包含字符 R、G 和 B。

输入

从标准输入中以以下格式给出输入：

$N$ $S$

输出

打印满足条件的三元组的数量。

示例输入1

4
RRGB

示例输出1

1

只有三元组 $(1,~3,~4)$ 满足两个条件。三元组 $(2,~3,~4)$ 满足第一个条件但不满足第二个条件，因此不计算在内。

示例输入2

39
RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB

示例输出2

1800