题目描述

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

当字符串$T_1$和$T_2$具有相同的长度时，如果对于每一个$i$（$1 \leq i \leq l$），$T_1$的第$i$个字符和$T_2$的第$i$个字符互补，则称它们是互补的。这里，A和T互补，C和G也互补。

请找出满足以下条件的非空连续子串$T$的数量：

• 存在一个字符串与$T$的排列互补。

这里，即使内容相同，我们认为来自$S$中不同位置的字符串是不同的。

约束条件

• $1 \leq N \leq 5000$
• $S$由A、T、C和G组成。

输入

从标准输入读入输入数据。输入格式如下：

$N$ $S$

输出

输出满足条件的非空连续子串$T$的数量。

示例输入1

4 AGCT

示例输出1

2

满足条件的两个子串如下：

• GC（第2到第3个字符）是CG的补，而且GC是CG的一个排列。
• AGCT（第1到第4个字符）是TCGA的补，而且AGCT是TCGA的一个排列。

示例输入2

4 ATAT

示例输出2

4

满足条件的四个子串如下：

• AT（第1到第2个字符）是TA的补，而且AT是TA的一个排列。
• TA（第2到第3个字符）是AT的补，而且TA是AT的一个排列。
• AT（第3到第4个字符）是TA的补，而且AT是TA的一个排列。
• ATAT（第1到第4个字符）是TATA的补，而且ATAT是TATA的一个排列。

示例输入3

10 AAATACCGCG

示例输出3

6