Let an array $[x_1,....,x_M]$ be good if and only if you can make it empty by performing any number of the following two types of operations:

1. If $x_i$ is divisible by $i$, divide $x_i$ by $i$.
2. If $x_i=1$, delete $x_i$. The elements to the right of $x_i$ are shifted left to accommodate the deletion.

Given an array $A=[a_1,...,a_N]$, count the number of good subarrays in $A$. Two good subarrays are counted separatedly if they span different indexes in $A$, even if the elements they contain are the same.

Constraints

$1\le N\le {10}^6$

$1\le a_i\le {10}^6$

Subtask 1 [50%]

$N\le 5000$

Subtask 2 [50%]

No additional constraints.

Input Specification

The first line contains a single integer, $N$.

The second line contains $N$ space-separated integers, $a_1,a_2,\dots ,a_N$.

Output Specification

Output a single line containing the number of good subarrays in $A$. Note that this number may be too large to fit in a 32-bit integer.

Sample Input

4
1 2 6 1

Sample Output

5

Explanation

For example, the array $[1,2,6]$ is good because, it can be made empty using the following operations:

• Divide the third element by $3$, resulting in the array $[1,2,2]$.
• Divide the second element by $2$, resulting the array $[1,1,2]$.
• Delete the first element, resulting in the array $[1,2]$.
• Divide the second element by $2$, resulting the array $[1,1]$.
• Delete the first element, resulting in the array $[1]$.
• Delete the first element, resulting in the empty array.