【题目描述】

有 $𝑛$个能量节点从左到右排成一行，编号为 $1,2,⋯,𝑛，$第 𝑖 个节点的能量值为整数 $a_𝑖$。

定义两个节点 $𝑥,𝑦$ 之间的能量差为 $|𝑎_𝑥−𝑎_𝑦|$。

现在有 𝑞 次相互独立的跃迁实验。每次实验给出两个参数 $𝑙,𝑟(1≤𝑙≤𝑟≤𝑛)$，跃迁者初始位于节点$𝑟$，目标是到达节点$𝑙$。

若当前跃迁者位于节点 $𝑤$，且 $𝑤>𝑙$，则下一次跃迁会跳到编号为

$max$ {$ 𝑘| 𝑙≤𝑘<𝑤,∀𝑖,𝑙≤𝑖<𝑤,|𝑎_𝑤−𝑎_𝑘|≥|𝑎_𝑤−𝑎_𝑖|$} 的节点。

也就是说，跃迁者会在区间 $[𝑙,𝑤−1]$ 中选择与当前节点能量差最大的节点；若有多个节点都能取得最大能量差，则选择编号最大的节点。

当跃迁者到达节点 𝑙 时，实验结束。由于每次跃迁都会跳到编号更小的节点，实验一定会在有限次跃迁后结束。

请你对每次实验求出从节点 𝑟 到节点 𝑙 所需要的跃迁次数。

特别地，若 𝑙=𝑟，则跃迁者一开始就在目标节点，答案为 0。

【输入格式】

从标准输入读入。

第一行包含一个正整数 𝑇，表示数据组数。

接下来依次输入 𝑇 组数据。

每组数据的第一行包含两个正整数 𝑛,𝑞，分别表示能量节点数量和实验次数。

第二行包含 𝑛 个整数 $𝑎_1,𝑎_2,⋯,𝑎_𝑛，$表示每个节点的能量值。

接下来 𝑞 行，每行包含两个正整数 𝑙,𝑟，表示一次跃迁实验。

【输出格式】

输出到标准输出。

对于所有数据中的每次实验，按照输入顺序输出答案。

每次实验输出一行，表示所需的跃迁次数。

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

3
2
2
3

【样例解释】

能量值依次为 𝑎=[5,1,9,4,10,2]。 对于第 1 次实验，𝑙=1,𝑟=6。从节点 6 出发，当前能量值为 2，候选区间为 [1,5]，各节点的能量差依次为 3,1,7,2,8，最大能量差为 8，所以第一次跃迁到节点 5。 四次实验的完整路径分别为：

1. l=1,r=6: 6 -> 5 -> 2 -> 1

2. l=2,r=6: 6 -> 5 -> 2

3. l=3,r=5: 5 -> 4 -> 3

4. l=1,r=4: 4 -> 3 -> 2 -> 1

所以输出分别为 3,2,2,3。

【数据范围】

对于所有数据，满足 $1≤𝑇，1≤𝑛,𝑞，∑𝑛,∑𝑞≤10^6，0≤𝑎_𝑖≤10^9，1≤𝑙≤𝑟≤𝑛$。