AT_arc130_a [ARC130A] Remove One Character

给定一个长度为 $N$ 的字符串 $S$。对于 $1 \leq i \leq N$，用 $S_i$ 表示从 $S$ 中删除第 $i$ 个字符后得到的字符串。 请计算满足以下条件的整数对 $(i, j)$ 的个数： - $1 \leq i < j \leq N$ - $S_i = S_j$

输入从标准输入中以如下格式给出： > $N$ $S$

请输出答案。

### 限制条件 - $2 \leq N \leq 3 \times 10^5$ - $S$ 是仅由小写英文字母组成的长度为 $N$ 的字符串 ### 样例解释 1 $S_i$ 依次为：`bbbcca`、`abbcca`、`abbcca`、`abbcca`、`abbbca`、`abbbca`、`abbbcc`。满足条件的 $(i, j)$ 有以下 $4$ 个： - $(i, j) = (2, 3)$ - $(i, j) = (2, 4)$ - $(i, j) = (3, 4)$ - $(i, j) = (5, 6)$ 由 ChatGPT 4.1 翻译