2019 North American Practice Contest 4

Start

2019-01-27 18:00 UTC

2019 North American Practice Contest 4

End

2019-01-27 23:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -205 days 19:19:18

Time elapsed

5:00:00

Time remaining

0:00:00

Problem E
GCDs

Given a sequence $A$ of $n$ numbers, define $f(lo,hi)$, $1 \le lo \le hi \le n$, as the Greatest Common Divisor of all the numbers $A_{lo}$ through $A_{hi}$, inclusive. Note that $lo$ and $hi$ are indices, not members of the list. Given an array, considering all possible values of $lo$ and $hi$, how many unique values of $f(lo,hi)$ will there be?

Input

There will be a single test case in the input. This test case will begin with a line with a single integer $n$ ($1 \le n \le 100\, 000$) representing the length of the sequence. The next $n$ lines will each have an integer $a$ ($1 \le a \le 100$). These are the numbers in the sequence, in sequence order.

Output

Output a single integer denoting the number of unique values $f(lo,hi)$ can have for the input sequence.

Sample Input 1 Sample Output 1
2
4
6
3
Sample Input 2 Sample Output 2
3
3
6
8
5