Problem

長さ $N$ の数列 $S$ があります。ここで数列 $S$ の各要素を整数 $i$ を用いて $S_i \ (0 \le i \lt N)$ と表します。

以下の条件を全て満たす整数の組 $(a, b, c)$ の個数を数えてください。

• $0 \le a \le b \lt N$
• $0 \le c \le b - a$
• 長さ $N$ の数列 $T$ の各要素 $T_i \ (0 \le i \lt N)$ を以下のように定めたとき、数列 $S$ が数列 $T$ と等しい。 \begin{equation*} T_i = \left \{ \begin{array}{ll} S_{a + ((i - a + c) \bmod (b - a + 1))}& {\rm if} \ \ \ a \le i \le b\\ S_i& {\rm otherwise} \\ \end{array} \right. \end{equation*}

ただし、非負整数 $x$ と 正の整数 $y$ に対し $x \bmod y$ とは $x$ を $y$ で割ったあまりを表します。

Input

入力は以下の形式で与えられる。

$N$
$S_0$ $S_1$ $...$ $S_{N-1}$

Constraints

入力は以下の条件を満たす。

• $1 \le N \le 2 \times 10^5$
• $0 \le $ $S_i$ $\le 10^9$
• 入力はすべて整数である

Ouput

答えを一行に出力せよ。

Sample Input 1

3
1 2 2

Sample Output 1

7

条件を満たす組は $(0,0,0),(0,1,0),(0,2,0),(1,1,0),(1,2,0),(1,2,1),(2,2,0)$ の $7$ 個です。

Sample Input 2

10
1 2 1 2 3 1 2 1 2 3

Sample Output 2

58

Sample Input 3

17
7 0 7 3 3 1 1 3 0 4 1 6 3 9 3 0 2

Sample Output 3

155

---