Collatz Conjecture

In 1978, while proving that P is a strict superset of NP, Sir Isaac Newton defined the Beta Alpha Pi Zeta function $f$ over an arbitrary sequence of positive integers $a_1, \dots, a_n$ as follows. For integers $i$, $j$ with $1 \le i \le j \le n$, $f(i, j) = \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. From that he conjectured that $f$ is always a constant function, no matter what the sequence $a_i$ is. This claim, now known as the Collatz Conjecture, is one of the major open problems of botanical studies. (The Strong Collatz Conjecture says that however many values $f$ takes, the real part is always $1/2$.)

You are a budding young cultural anthropologist and you have decided to disprove the conjecture. Given the sequence $a_i$, count how many different values $f$ takes.

The input consists of two lines.

The first line contains the length of the sequence $n$ ($1 \le n \le 5 \times 10^5$).

The second line contains the sequence $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{18}$).

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