Good Subsegments

You are given a sequence of integers. A subsegment is defined as a contiguous subsequence of the original sequence. A subsegment is called "good" if the greatest common divisor ((\gcd)) of all its elements is equal to 1. Your task is to count the total number of good subsegments in the sequence.

For example, consider the sequence [2, 3, 4]:

• The subsegment [2, 3] has (\gcd(2, 3) = 1), so it is good.
• The subsegment [3, 4] has (\gcd(3, 4) = 1), so it is good.
• The subsegment [2, 3, 4] has (\gcd(2, 3, 4) = 1), so it is good.

Thus, the output would be 3 for this case.

Note: The input is read from standard input and the output should be printed to standard output.

inputFormat

The first line contains a single integer (n) (the length of the sequence). The second line contains (n) integers separated by spaces which represent the sequence.

outputFormat

Print a single integer: the total number of good subsegments whose (\gcd) equals 1.## sample

3
2 3 4

3