题目描述

给定长度为$N$的字符串$S$。对于每个$1\leq i\leq N$，令$S_i$表示通过从$S$中删除第$i$个字符获得的字符串。

找到满足以下两个条件的整数对$(i,j)$的数量。

• $1\leq i < j\leq N$
• $S_i = S_j$

约束条件

• $2\leq N\leq 3\times 10^5$
• $S$是一个由小写英文字母组成的长度为$N$的字符串。

输入

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

$N$ $S$

输出

打印答案。

示例输入1

7
abbbcca

示例输出1

4

以下按顺序显示了字符串$S_i$：bbbcca，abbcca，abbcca，abbcca，abbbca，abbbca，abbbcc。

满足条件的四对$(i,j)$如下：

• $(i,j) = (2,3)$
• $(i,j) = (2,4)$
• $(i,j) = (3,4)$
• $(i,j) = (5,6)$

示例输入2

4
xxxx

示例输出2

6

示例输入3

2
pp

示例输出3

1

示例输入4

2
st

示例输出4

0