You are given an array $a_1, a_2, \ldots, a_n$ of $n$ positive integers.

A triplet of indices $(i, j, k)$ is called happy if $1 \le i < j < k \le n$ and $\gcd(a_i, a_j, a_k) = k - i + 1$.

Count the number of happy triplets in $a$.

Input

The first line contains a single integer $n$ ($3 \le n \le 5 \times 10^4$), the length of the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_{n}$ ($1 \le a_i \le 10^5$), the elements of the array.

Output

Print a single integer: the number of happy triplets.

Example

stdin

6
6 3 12 8 4 20

stdout

3

Note

The happy triplets in the example are:

• $(1, 2, 3)$: $\gcd(6, 3, 12) = 3$, and $3 - 1 + 1 = 3$;
• $(3, 4, 6)$: $\gcd(12, 8, 20) = 4$, and $6 - 3 + 1 = 4$;
• $(3, 5, 6)$: $\gcd(12, 4, 20) = 4$, and $6 - 3 + 1 = 4$.