Greatest common divisor for all subsegments

Go Hard math

Task «Greatest common divisor for all subsegments»

Given an array of integers a of length n. For each possible subsegment [l, r] (1 ≤ l ≤ r ≤ n), it is necessary to compute the greatest common divisor (GCD) of the elements of this subsegment. Then, among all obtained GCDs, find the number of distinct values. An efficient algorithm must be implemented, considering that n can be up to 100,000 and the array elements up to 10^9.

Input Format

The first line contains a single integer n (1 ≤ n ≤ 100000). The second line contains n integers a_i (1 ≤ a_i ≤ 10^9), separated by spaces.

Output Format

Output a single integer — the number of distinct GCD values among all subsegments of the array.

Examples

Example 1

INPUT

3
6 10 15

OUTPUT

6

Example 2

INPUT

4
2 4 8 16

OUTPUT

4

Example 3

INPUT

5
7 14 21 28 35

OUTPUT

5

Example 4

INPUT

5 10 15

OUTPUT

3

main.go