Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

The Total Score of an Array

By S_Rifat · Limits 2s, 512 MB

Let’s say, min is the minimum element of an array and max is the maximum element of an array. The score of an array is defined as the number of integers in the range from min to 2 * max which can not be divided by any of the elements of the array. The total score of an array is defined as the sum of the score of the sub-arrays which are also the suffix of the array. You will be given an array. Show the total score of the array.

Input

The first line of input consists of a single integer nn — the length of the array.

The next line consists of nn integers a1,a2,a3,.ana_1, a_2, a_3, ……. a_n— the elements of the array.

1<=n<=10000001 <= n <= 1000000

1<=ai<=20000001 <= a_i <= 2000000

Output

Output a single integer that denotes the total score of the array.

Sample

InputOutput
2
2 3
3

In the sample test case, the given array is [2,3][2, 3]. The array has two sub-arrays which are also the suffix of the array. They are [2,3][2, 3] and [3][3].

In sub array [2,3]: min=2,max=3=>2max=23=6.Range:[2,3,4,5,6]min = 2, max = 3 => 2 * max = 2 * 3 = 6. Range: [2, 3, 4, 5, 6]. In the range, 55 is not divisible by any of the elements of the sub array. So, the score is 1.

In sub array [3]: min=3,max=3=>2max=23=6.Range:[3,4,5,6]min = 3, max = 3 => 2 * max = 2 * 3 = 6. Range: [3, 4, 5, 6]. In the range, 44 and 55 are not divisible by any of the elements of the sub array. So, the score is 2.

So, the total score is 1+2=3.1 + 2 = 3.

    Discussion

    Statistics


    74% Solution Ratio

    pathanEarliest, 3w ago

    NJRafiFastest, 0.1s

    NJRafiLightest, 5.0 MB

    NirjhorShortest, 802B

    Submit

    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.