[WC2022] 秃子酋长

5s 512M -O2

传说在明斯克航空航天局中，有一名强大的秃子酋长。 秃子酋长法力无边，他的头上没有头发，而且头特别硬，跑得还不慢。 这一天，豌豆射手来到了明斯克航空航天局。 秃子酋长为了考验这一位新人，给他出了这样一道题： 给一个长为 $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$。 **【数据范围】** 对 $10\%$ 的数据，$n, m \leq 10^3$； 对另外 $10\%$ 的数据，$n, m \leq 5 \times 10^4$； 对另外 $10\%$ 的数据，$n, m \leq 10^5$； 对另外 $10\%$ 的数据，$n, m \leq 2 \times 10^5$； 对另外 $20\%$ 的数据，$|a_i - i| \leq 10$； 对另外 $20\%$ 的数据，$m=\dfrac{n(n-1)}{2}$； 对其余数据，无特殊限制。 对于 $100\%$ 的数据，满足 $1 \leq n, m \leq 5\times 10^5$，$1 \leq a_i \leq n$，$a_i$ 互不相同，$1 \leq l \leq r \leq n$，所有数值为整数。