In 1978 AD the great Sir Isaac Newton, whilst proving that $\mathcal{P}$ is a strict superset of $\mathcal{NP}$, defined the Beta Alpha Pi Zeta function $f$ as follows over any sequence of positive integers $a_1, \dots , a_ n$. Given integers $1\leq i\leq j\leq n$, we define $f(i, j)$ as $\gcd (a_ i, a_{i+1}, \dots , a_{j-1}, a_ j)$. 

About a century later Lothar Collatz applied this function to the sequence $1, 1, 1, \dots , 1$, and observed that $f$ always equalled $1$. Based on this, he conjectured that $f$ is always a constant function, no matter what the sequence $a_ i$ is. This conjecture, now widely known as the Collatz Conjecture, is one of the major open problems in botanical studies. (The Strong Collatz Conjecture claims that however many values $f$ takes on, the real part is always $\frac{1}{2}$.)

You, a budding young cultural anthropologist, have decided to disprove this conjecture. Given a sequence $a_ i$, calculate how many different values $f$ takes on.

-----Input-----
The input consists of two lines.
 - A single integer $1 \leq n \leq 5 \cdot 10^5$, the length of the sequence.
 - The sequence of integers $a_1, a_2, \dots , a_ n$. It is given that $1 \leq a_ i \leq 10^{18}$.

-----Output-----
Output a single line containing a single integer, the number of distinct values $f$ takes on over the given sequence.

-----Examples-----
Sample Input:
4
9 6 2 4
Sample Output:
6

Source: kattis | Difficulty: HARD


Solutions: