#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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 ≤ *A _{i}* ≤ 10

^{9}.

Subtask 1 (13%): 1 ≤ *N* ≤ 10^{6}; *A _{i}* = 1.

Subtask 2 (31%): 1 ≤ *N* ≤ 10 000.

Subtask 3 (56%): 1 ≤ *N* ≤ 10^{6}.

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}.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 13 | 10 | 1s | 256MB | Minimum |

2 | 31 | 11 | 1s | 256MB | Minimum |

3 | 56 | 32 | 1s | 256MB | Minimum |

4 | 0 | 1 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o singularity -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512