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 \leq N \leq 10^6~

~1 \leq a_i \leq 10^6~

Subtask 1 [50%]

~N \leq 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.