D. Good Pairs Again
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the qualifying round of the olympiad, you solved the problem "Good Pairs." Recall that an unordered pair of natural numbers is called good if one of them divides the other.

While preparing the problem from the qualifying round, the jury encountered the following issue. To verify the correctness of the solution, it is necessary to quickly find the number of good pairs that can be formed from the numbers output by the participant's program. The jury managed to solve this problem, but can you?

More formally: you are given $$$n$$$ natural numbers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$. Find the number of such pairs of indices $$$i$$$, $$$j$$$, where $$$i \lt j$$$, such that $$$a_i$$$ divides $$$a_j$$$ or $$$a_j$$$ divides $$$a_i$$$.

Input

The first line of input contains a natural number $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of numbers.

In the next $$$n$$$ lines, the integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ are given, where $$$1 \le a_i \le 10^6$$$.

Output

Output a single integer — the number of good pairs that can be formed from the input numbers.

Scoring

Subtask 1 (up to 20 points): $$$n \le 1000$$$.

Subtask 2 (up to 40 points): all $$$a_i$$$ do not exceed 1000.

Subtask 3 (up to 40 points): there are no additional constraints.

Examples
Input
3
2
5
10
Output
2
Input
2
1
1
Output
1
Note

Note that the answer may exceed the possible value of a 32-bit integer variable. Therefore, it is necessary to use a 64-bit integer data type (type int64 in Pascal, type long long in C++, type long in Java and C#). In Python, no additional actions are required.