给定一个长度为 $N$ 的数列 $A$ 和 $Q$ 次询问。每次询问由两个数 $L$ 和 $R$ 描述。在每次询问前，所有不满足条件 $L \le A_i \le R$ 的元素都会被删除。设剩余的序列为 $X$，你需要计算以下值：$|X_1 - X_2| + |X_2 - X_3| + \dots + |X_{k-1} - X_k|$，其中 $k$ 是 $X$ 中元素的个数。处理完询问后，所有被删除的元素都会恢复。注意，当 $k \le 1$ 时，答案为 $0$。

输入格式

第一行包含两个正整数 $N$ 和 $Q$ ($1 \le N, Q \le 200000$)，分别表示序列中元素的个数和询问的次数。

第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^9$)，描述序列 $A$。

接下来 $Q$ 行，每行包含两个整数 $L$ 和 $R$ ($1 \le L, R \le 10^9$)，描述询问。

输出格式

对于每次询问，输出答案——剩余子序列中每对相邻元素绝对差之和。

子任务

本题由 8 个子任务组成，满足以下约束：

1. $N, Q \le 1000$。分值 7 分。
2. $a_i \le a_{i+1}$。分值 9 分。
3. $a_i \le 300$。分值 10 分。
4. $l_i \le l_{i+1}, r_i \le r_{i+1}$。分值 13 分。
5. $N, Q \le 50000$。分值 10 分。
6. $N, Q \le 75000$。分值 11 分。
7. $N, Q \le 100000$。分值 11 分。
8. 原始问题约束。分值 29 分。

样例

输入 1

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

输出 1

0
14
4
0
0
20
11
0
0
10