問題文

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

出力

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

入力例 1

7
abbbcca

出力例 1

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

入力例 2

4
xxxx

出力例 2

6

入力例 3

2
pp

出力例 3

1

入力例 4

2
st

出力例 4

0