给定序列 $a_1,\dots,a_n$ ，$m$ 次询问，每次询问给出 $l,r$ ，问有多少组 $(i,j,k)$ 满足 $l\le ia_j$ 。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数 $a_1,\dots,a_n$。

接下来 $m$ 行每行两个整数 $l,r$ 表示一个询问。

输出格式

共 $m$ 行，每行一个整数，依次表示每个询问的答案。

样例数据

样例输入

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

样例输出

4
4
1
0
0

子任务

Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078

所有数值为整数。

对于 $100\%$ 的数据，满足 $1\le a_i\le n$，$1\le l\le r\le n$，$n,m\le 5\times 10^5$。