题目描述

给定一个长度为 $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$

输出格式

请输出答案。

样例 1

输入

7
abbbcca

输出

4

样例 2

输入

4
xxxx

输出

6

样例 3

输入

2
pp

输出

1

样例 4

输入

2
st

输出

0

说明/提示

限制条件

• $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 翻译