Hide

Problem S
Collatz Conjecture

Languages en ja

Picture by mscolly via Flickr.

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.

Sample Input 1	Sample Output 1
4 9 6 2 4	6

Sample Input 2	Sample Output 2
4 9 6 3 4	5

Problem SCollatz Conjecture

Input

Output

Problem S
Collatz Conjecture