Dynamic Programming Optimization with Convex Hull Trick
Given an array a of N numbers , you have to find the number of pair of indices i and j that satisfy the following relation:
- i < j
- ai > aj
- gcd( ai , aj )=1
Input
The first line of the input contains a single integer N - denoting the size of the array.
The next line contains N space separated integers denoting the array a.
Output
Output a single integer - the answer to the problem stated above.
Constraints
1<=N<=105
1<=ai<=105
