Remove One Character

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

题目描述

给定一个长度为 $N$ 的字符串 $S$。对每个 $1\le i\le N$，记 $S_i$ 为从 $S$ 中删除第 $i$ 个字符后得到的字符串。

求满足 $1\le i<j\le N$ 且 $S_i=S_j$ 的整数对 $(i,j)$ 的数量。

输入格式

第一行输入整数 $N$。

第二行输入仅由小写英文字母组成的字符串 $S$。

输出格式

输出满足条件的整数对数量。

样例输入 1

7
abbbcca

样例输出 1

4

样例输入 2

4
xxxx

样例输出 2

6

样例输入 3

2
pp

样例输出 3

1

样例输入 4

2
st

样例输出 4

0

数据范围

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