콜라츠 추측

1978년, 아이작 뉴턴 경은 P가 NP의 진상위집합임을 증명하던 도중 양의 정수 수열 $a_1, \dots, a_n$ 위에서 베타 알파 파이 제타 함수 $f$를 다음과 같이 정의했다. $1 \le i \le j \le n$을 만족하는 정수 $i$, $j$에 대해 $f(i, j) = \gcd(a_i, a_{i+1}, \dots, a_{j-1}, a_j)$이다.

약 100년 뒤 로타어 콜라츠는 이 함수를 수열 $1, 1, 1, \dots, 1$에 적용했고, $f$가 언제나 1이라는 사실을 관찰했다. 콜라츠는 여기서 수열 $a_i$가 무엇이든 $f$는 항상 상수 함수라고 추측했다. 오늘날 콜라츠 추측이라 부르는 이 명제는 식물학의 주요 미해결 문제 중 하나다. (강한 콜라츠 추측은 $f$가 취하는 값이 몇 개이든 실수부는 항상 $1/2$이라고 주장한다.)

신진 문화인류학자인 당신은 이 추측을 반증하기로 했다. 수열 $a_i$가 주어지면 $f$가 취하는 서로 다른 값이 몇 개인지 구하라.

입력은 두 줄이다.

첫째 줄에 수열의 길이 $n$ ($1 \le n \le 5 \times 10^5$)이 주어진다.

둘째 줄에 수열 $a_1, a_2, \dots, a_n$이 주어진다. ($1 \le a_i \le 10^{18}$)

주어진 수열에서 $f$가 취하는 서로 다른 값의 개수를 한 줄에 출력한다.