omogen

Task

A sequence $(i, j)$ with elements $a_i, a_{i+1}, \dots, a_j$ is homogeneous if, for any two chosen positions $x$ and $y$ with $x \neq y$, the elements $a_x$ and $a_y$ are coprime.

You are given a sequence of length $n$ with nonzero positive integers. Determine the number of its homogeneous subsequences.

Input data

The first line will contain the number $n$, representing the length of the sequence.
The second line will contain the $n$ values of the sequence $a$, separated by spaces.

Output data

The first line of the output file will contain the number of homogeneous subsequences of the sequence.

Constraints and clarifications

• $1 \leq N \leq 1000000$.
• $1 \leq a_i \leq 10^7$, for $i$ $\in {[} 1, n {]}$.

Example

stdin

8
7 2 4 2 1 5 1 1

stdout

19

Explanation

For example, one of the $19$ homogeneous sequences is $[2, 1, 5]$ because $gcd(2, 1) = 1$, $gcd(2, 5) = 1$, and $gcd(1, 5) = 1$.

On the other hand, the sequence $[4, 2, 1]$ is not homogeneous because $gcd(4, 2) = 2$.