题目背景

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$，所有数值为整数。