#ABC162D. RGB Triplets

RGB Triplets

题目描述

We have a string SS of length NN consisting of R, G, and B.

Find the number of triples (i, j, k) (1i<j<kN)(i,~j,~k)~(1 \leq i \lt j \lt k \leq N) that satisfy both of the following conditions:

  • SiSjS_i \neq S_j, SiSkS_i \neq S_k, and SjSkS_j \neq S_k.
  • jikjj - i \neq k - j.

我们有一个长度为 NN 的字符串 SS ,由 RGB 组成。

求同时满足以下两个条件的三元组 (i, j, k) (1i<j<kN)(i,~j,~k)~(1 \leq i \lt j \lt k \leq N) 的个数:

  • SiSjS_i \neq S_j , SiSkS_i \neq S_k , 和 SjSkS_j \neq S_k
  • jikjj - i \neq k - j .

输入格式

输入内容按以下格式标准输入:

NN
SS

输出格式

打印有关三联体的数量。

样例 #1

样例输入 #1

4
RRGB

样例输出 #1

1

样例 #2

样例输入 #2

39
RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB

样例输出 #2

1800

说明

数据规模与约定

  • 1N40001 \leq N \leq 4000
  • SS 是长度为 NN 的字符串,由 RGB 组成。

样例 11 解释

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