inverted-gcd

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:  
1. i < j     
2. ai > aj
3. 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 ≤ 10^5
1 ≤ ai ≤ 10^5

SAMPLE INPUT
4
4 2 8 1

SAMPLE OUTPUT
3

Explanation

The indices that satisfy the given condition are (1,4) , (2,4) and (3,4).

Source: hackerearth | Difficulty: MEDIUM_HARD


Solutions: