The Total Score of an Array

Let’s say, min is the minimum element of an array and max is the maximum element of an array. The score of an array is defined as the number of integers in the range from min to 2 * max which can not be divided by any of the elements of the array. The total score of an array is defined as the sum of the score of the sub-arrays which are also the suffix of the array. You will be given an array. Show the total score of the array.

Input

The first line of input consists of a single integer $n$ — the length of the array.

The next line consists of $n$ integers $a_1, a_2, a_3, ……. a_n$— the elements of the array.

$1 <= n <= 1000000$

$1 <= a_i <= 2000000$

Output

Output a single integer that denotes the total score of the array.

Sample

Input	Output
2 2 3	3

In the sample test case, the given array is $[2, 3]$. The array has two sub-arrays which are also the suffix of the array. They are $[2, 3]$ and $[3]$.

In sub array [2,3]: $min = 2, max = 3 => 2 * max = 2 * 3 = 6. Range: [2, 3, 4, 5, 6]$. In the range, $5$ is not divisible by any of the elements of the sub array. So, the score is 1.

In sub array [3]: $min = 3, max = 3 => 2 * max = 2 * 3 = 6. Range: [3, 4, 5, 6]$. In the range, $4$ and $5$ are not divisible by any of the elements of the sub array. So, the score is 2.

So, the total score is $1 + 2 = 3.$