#1297. 复习笔记

不知道怎么回事，Leohh用来写复习笔记的活页本被弄乱了，页码乱七八糟。但是Leohh偶然发现按照这样的顺序，连续复习中间的某些笔记，可以起到随机抽检巩固记忆的效果。

具体来说，复习笔记总共有 $n$ 页，现在从前往后的页码分别为 $a_1,a_2,\cdots,a_n$ ，是一个 $1,2,\cdots,n$ 的排列。复习 $a_l,a_{l+1},\cdots,a_{r-1},a_r$ 这些页的复习效果等于二元组 $(x,y)$ 的个数，其中 $(x,y)$ 满足 $l\leq x,y\leq r$ 且 $a_y|a_x$ 。

现在有 $m$ 个询问，第 $i$ 个询问给定 $l_i,r_i$ ，问你复习 $a_{l_i},a_{l_i+1},\cdots,a_{r_i-1},a_{r_i}$ 这些页的复习效果是多少。

第一行两个整数 $n,m$ ，表示总页数和询问数

第二行 $n$ 个整数，表示从前往后的页码

接下来 $m$ 行，每行两个整数 $l_i,r_i$ ，表示询问的范围

共 $m$ 行，对于每次询问，输出复习效果的值

样例输入

8 4
3 5 4 1 2 7 6 8
1 4
2 6
5 8
1 8

样例输出

7
10
6
20

$1\leq n,m\leq 2\times 10^5,\ 1\leq a_i\leq n,\ 1\leq l_i\leq r_i\leq n$