Divisor Pairs

Time limit2sMemory limit512 MB

Summary

Given n integers, count ordered pairs (i, j) with i != j such that a_i divides a_j.

Level: Medium4 of 10
Topics: Math, Array, Number theory, Implementation
Solved: No attempts yet

Problem

You are given a sequence of $n$ integers $a_1, a_2, \ldots, a_n$ . Count the ordered pairs $(i, j)$ with $i, j \in \{1, \ldots, n\}$ , $i \neq j$ , such that $a_i$ is a divisor of $a_j$ .

Input

The first line contains one integer $n$ ( $1 \leq n \leq 2,000,000$ ).

The second line contains the $n$ integers $a_1, a_2, \ldots, a_n$ of the sequence ( $1 \leq a_i \leq 2,000,000$ ).

Output

Print one integer on the first line: the number of ordered pairs that satisfy the condition.

Hint

In the first sample there are 6 pairs with the required property: $(1, 2)$ , $(1, 4)$ , $(1, 5)$ , $(4, 1)$ , $(4, 2)$ , $(4, 5)$ .

Examples4

Example 1
Input
```
5
2 4 5 2 6
```
Expected output
```
6
```
Example 2
Input
```
1
7
```
Expected output
```
0
```
Example 3
Input
```
4
7 7 7 7
```
Expected output
```
12
```
Example 4
Input
```
3
1 1 3
```
Expected output
```
4
```