题目描述

给定一个长度为 $N$ 的字符串 $S$。对于每个 $1 ≤ i ≤ N$，令 $S_i$ 表示从 $S$ 中删除第 $i$ 个字符后得到的字符串。
找出满足以下两个条件的整数对$(i,j)$ 的数量：

1. $1 ≤ i < j ≤ N$

2. $S_i = S_j$

输入格式

输入$N$和$S$。

输出格式

输出所求答案。

样例

7
abbbcca

4

4
xxxx

6

2
pp

1

2
st

0

样例1解释

以下是按顺序的 $S_i$ 字符串：bbbcca, abbcca, abbcca, abbcca, abbbca, abbbca, abbbcc。

以下 $4$ 对 $(i,j)$ 满足条件：

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

数据范围

数据范围：$2 ≤ N ≤ 3 × 10^5$,$S$是一个由小写英文字母组成的长度为 $N$ 的字符串。

来源

• AtCoder ARC130A