给一个长为 $n$ 的排列 $a_1,\dots, a_n$，有 $m$ 次询问，每次询问区间 $[l, r]$ 内，排序后相邻的数在原序列中的位置的差的绝对值之和。

输入格式

第一行两个数表示 $n, m$；

之后一行 $n$ 个数依次表示序列 $a$ 中的元素；

之后 $m$ 行，每行两个数 $l, r$ 表示一次查询。

输出格式

对于每次询问，输出一行一个数表示答案。

样例数据

样例输入

5 2
5 4 2 3 1
3 4
2 5

样例输出

1
5

样例解释

第一个询问，$2,3$ 排序后为 $2,3$，在原序列中的位置为 $3,4$，相邻元素在原序列中位置差的绝对值之和为 $|3 - 4| = 1$。

第二个询问，$4, 2, 3, 1$ 排序后为 $1, 2, 3, 4$，在原序列中的位置为 $5, 3, 4, 2$，相邻元素在原序列中位置差的绝对值之和为 $|5 - 3| + |3 - 4| + |4 - 2| = 5$。

子任务

Idea：?，Solution：ccz181078，Code：nalemy，Data：ccz181078

对于 $100\%$ 的数据，满足 $1 \leq n, m \leq 2\times 10^6$，$1 \leq a_i \leq n$，$a_i$ 互不相同，$1 \leq l \leq r \leq n$，所有数值为整数。