Killjee and non-co-prime subarray

4

4 votes
Mathematics, Medium, Greatest common divisor, Greatest common divisor
Problem

Killjee has a very easy problem for you. You need to find number of non-co-prime sub-arrays for a given array a containing n elements.

A sub-array of array a is called non-co-prime if gcd(al,al+1,_____,ar) 1. Where sub-array contains elements al,al+1,_____,ar.

INPUT CONSTRAINTS
1n105

1ai105

INPUT FORMAT
First line of input contains a single integer n, denoting number of elements in array a.

Next line contains n space separated integers, elements of array a.

OUTPUT FORMAT
output a single integer number of non-co-prime sub-arrays.

Time Limit: 0.5
Memory Limit: 256
Source Limit:
Explanation

{2},{4},{3},{5},{2,4} are 4 subarrays which has gcd greater than 1.

Editor Image

?