Divisible Inversions

Interview

Time limit2sMemory limit512 MB

Summary

Given a permutation of 1 to n, count pairs i < j where p[i] is a multiple of p[j].

Level: Medium6 of 10
Topics: Array, Math, Number theory, Binary search
Solved: No attempts yet

Problem

Recently, Vasya learned how to count the number of inversions in a permutation with a Fenwick tree. Petya considers that an easy problem, so he decided to make a harder one. Petya asked Vasya to count the inversions in which one element divides the other evenly. Formally, given the permutation $(p_{1}, p_{2}, \ldots, p_{n})$ , the task is to find the number of pairs of indices $(i, j)$ such that $i < j$ and $p_{i}$ is a multiple of $p_{j}$ .

Help Vasya solve this problem.

Input

The first line contains an integer $n$ , the length of the permutation ( $1 \le n \le 100\,000$ ). The second line contains $n$ space-separated integers $p_{i}$ . The given integers are guaranteed to form a permutation of the integers from $1$ to $n$ .

Output

Print one integer: the number of divisible inversions in the given permutation.

Examples2

Example 1
Input
```
5
1 4 3 2 5
```
Expected output
```
1
```
Example 2
Input
```
5
5 4 3 2 1
```
Expected output
```
5
```