题目描述

给定\(1 \sim N\)的一个全排列\(\{p_i\}, i=1,2 \cdots N\)，现有\(Q\)次询问，每次询问给定两个参数\(1 \le L_i < R_i \le N\)，求有多少个正整数对\((i, j)\)满足\(L_i \le i, j \le R_i, \quad i \ne j\)且\(p_i\)可以被\(p_j\)整除。

输入格式

第一行是两个正整数\(N, Q\)，表示序列的长度以及询问的个数；
第二行是\(N\)个正整数\(p_1 \cdots p_N\)，输入保证序列为\(1 \sim N\)的一个全排列；
之后\(Q\)行，每行两个正整数\(L_i, R_i\)，表示该次询问的参数，输入保证\(1 \le L_i < R_i \le N\)。

输出格式

输出\(Q\)行，每行一个非负整数，表示该次询问的答案。

样例

输入

5 5
3 2 5 1 4
1 3
2 4
3 5
1 4
2 5

输出

0
2
2
3
4

数据规模及约定

20%的数据：\(2 \le N, Q \le 200\)
40%的数据：\(2 \le N, Q \le 2,000\)
70%的数据：\(2 \le N, Q \le 20,000\)
100%的数据：\(2 \le N, Q \le 200,000\)
所有数据的生成流程均遵循如下的伪代码（其中随机函数rand(x, y)以均匀的概率返回闭区间\([x, y]\)之内的任一整数）：

input N, Q
output N, Q to destination file F
arr[1..N] = {1, 2 ... N} after random shuffle
output arr[1..N] to F
for i = 1 to Q
    length = rand(2, N)
    left = rand(1, N - length + 1)
    output left, left + length - 1 to F

时间限制1s，空间限制512MB。