DNA Sequence

时间限制：2s
空间限制：1024MB

题目描述

有一个长度为 $N$、仅由 A、T、C、G 组成的字符串 $S$。

两个等长字符串被称为互补的，如果它们每一对对应位置上的字符分别是 A 与 T，或分别是 C 与 G，同一对中两个字符的先后顺序不限。

求 $S$ 有多少个非空连续子串 $T$，满足：存在一种 $T$ 的字符重排，使重排后的字符串与 $T$ 互补。位置不同的子串分别计数。

输入格式

一行输入整数 $N$ 和字符串 $S$。

输出格式

输出满足条件的连续子串数量。

样例输入 1

4 AGCT

样例输出 1

2

样例输入 2

4 ATAT

样例输出 2

4

样例输入 3

10 AAATACCGCG

样例输出 3

6

数据范围

• $1\le N\le 5000$；
• $S$ 仅由 A、T、C、G 组成。