Problem Description
A range of numbers with a gcd (greatest common divisor) of 1 is known as a "singularity" range.
Damian has an array A of N numbers and wonders how many singularity ranges there are.
Can you help him?
Input
The first line contains one integer, N, the number of integers.
The second line contains N space-separated integers, representing the numbers of the array.
Output
The output should contain one line containing one integer, the number of ranges with a gcd of 1.
Limits
For all subtasks, 1 ≤ Ai ≤ 109.
Subtask 1 (13%): 1 ≤ N ≤ 106; Ai = 1.
Subtask 2 (31%): 1 ≤ N ≤ 10 000.
Subtask 3 (56%): 1 ≤ N ≤ 106.
Subtask 4 (0%): Sample Testcases.
Sample Testcase 1
Input
4
2 9 7 14
Output
5
Sample Testcase 1 Explanation
The ranges are {2, 9}, {9, 7}, {2, 9, 7}, {9, 7, 14}, {2, 9, 7, 14}.