配点 : $300$ 点

問題文

長さ $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$

出力

答えを出力してください。

7
abbbcca

4

$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)$

4
xxxx

6

2
pp

1

2
st

0