RGB Triplets
Problem
We have a string S of length N consisting of 'R' , 'G' and 'B'.
Find the number of triples (i, j, k) (1 ≤ i < j < k ≤ N) that satisfy both of the following conditions:
- Si ≠ Sj , Si ≠ Sk , and Sj ≠ Sk.
- j−i ≠ k−j.
Constraints
- 1 ≤ N ≤ 4000
- S is a string of length N consisting of 'R', 'G' and 'B'.
Input
Input is given from Standard Input in the following format:
N S
Output
Print the number of triplets in question.
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation
Only the triplet (1, 3, 4) satisfies both conditions. The triplet (2, 3, 4) satisfies the first condition but not the second, so it does not count.
