题目大意：给一个长为 $n$ 的排列 $a_1,\dots, a_n$，有 $m$ 次询问，每次询问区间 $[l, r]$ 内，排序后相邻的数在原序列中的位置的差的绝对值之和。
题目背景
题目描述
传说在明斯克航空航天局中，有一名强大的秃子酋长。
秃子酋长法力无边，他的头上没有头发，而且头特别硬，跑得还不慢。
这一天，豌豆射手来到了明斯克航空航天局。
秃子酋长为了考验这一位新人，给他出了这样一道题：
给一个长为 $n$ 的排列 $a_1,\dots, a_n$，有 $m$ 次询问，每次询问区间 $[l, r]$ 内，排序后相邻的数在原序列中的位置的差的绝对值之和。
输入输出格式
输入格式
第一行两个数表示 $n, m$；
之后一行 $n$ 个数依次表示序列 $a$ 中的元素；
之后 $m$ 行，每行两个数 $l, r$ 表示一次查询。
输出格式
输入输出样例
输入样例 #1
5 2
5 4 2 3 1
3 4
2 5输出样例 #1
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$，所有数值为整数。
解题思路
莫队：将区间的数字逐个放入set中，边插入边维护答案。新增的数字在两端，只需要增加差值；否则，需要先减少两边数字差值，再加上自己与两边数字的差值之和，时间复杂度$O(n\sqrt{n}log_2n)$。
回滚莫队：数组插入是O(n)的，但是删除是O(1)的，我们可以尝试将插入操作改为删除操作。预处理好[1, n]的答案，对于每一种块，左端点的移动是根号的，右端点的移动我们让他递减，这样就可以实现右端点删除之和为O(n)。左端点删除和回滚都是根号的，执行至多m次。遇到新的块根号次，初始化每次O(n)，用内存函数速度稍快。总的时间复杂度是$O(n\sqrt{n}+m\sqrt{n})$。
程序实现
