問題文

英小文字からなる長さ N の文字列 S=S_1 S_2 \dots S_N があります。以下の操作をちょうど 1 回行うとき、最終的な S としてありうる文字列の種類数を求めてください。

• 1 \le l \le r \le N を満たす整数 l, r を選び、S の l 文字目から r 文字目までを取り除く。つまり、操作後の S は S_1S_2\dots S_{l-1}S_{r+1}\dots S_N となる。

制約

• N は整数
• 1 \leq N \leq 5 \times 10^5
• S は英小文字からなる長さ N の文字列

入力例 1

5
abbab

出力例 1

11

得られる S としてありうるものは以下の 11 通りです。

• 空文字列
• a
• aab
• ab
• abab
• abb
• abba
• abbb
• b
• bab
• bbab

入力例 2

5
aaaaa

出力例 2

5

入力例 3

4
utpc

出力例 3

10