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.
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 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 |