A9040. Yaroslav and Divisors

Yaroslav has an array $p=p_{1},p_{2},...,p_{n}$ $(1<=p_{i}<=n)$ , consisting of $n$ distinct integers. Also, he has $m$ queries:

- Query number $i$ is represented as a pair of integers $l_{i}$ , $r_{i}$ $(1<=l_{i}<=r_{i}<=n)$ .
- The answer to the query $l_{i},r_{i}$ is the number of pairs of integers $q$ , $w$ $(l_{i}<=q,w<=r_{i})$ such that $p_{q}$ is the divisor of $p_{w}$ .

Help Yaroslav, answer all his queries.

The first line contains the integers $n$ and $m$ $(1<=n,m<=2·10^{5})$ . The second line contains $n$ distinct integers $p_{1},p_{2},...,p_{n}$ $(1<=p_{i}<=n)$ . The following $m$ lines contain Yaroslav's queries. The $i$ -th line contains integers $l_{i},r_{i}$ $(1<=l_{i}<=r_{i}<=n)$ .

Print $m$ integers — the answers to Yaroslav's queries in the order they appear in the input.

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.