×

计蒜客

  1. 题库
  2. query
  3. 问答
  • 29.45%
  • 262144K

Given a permutation $p$ of length $n$, you are asked to answer $m$ queries, each query can be represented as a pair $(l ,r )$, you need to find the number of pair$(i ,j)$ such that $l \le i < j \le r$ and $\min(p_i,p_j) = \gcd(p_i,p_j )$.

Input

There is two integers $n(1 \le n \le 10^5)$, $m(1 \le m \le 10^5)$ in the first line, denoting the length of $p$ and the number of queries.

In the second line, there is a permutation of length $n$, denoting the given permutation $p$. It is guaranteed that $p$ is a permutation of length $n$.

For the next $m$ lines, each line contains two integer $l_i$ and $r_i(1 \le l_i \le r_i \le n)$, denoting each query.

Output

For each query, print a single line containing only one integer which denotes the number of pair$(i,j)$.

样例输入

3 2
1 2 3
1 3
2 3

样例输出

2
0

想挑战这道题吗

  • main.c