时间限制：1秒　　内存限制：256M

---

【题目描述】

　　每天，农夫FJ的 \(N\) 头奶牛总是按相同一序列排队。有一天，FJ决定让一些牛们玩一场飞盘比赛。他准备找一群在队列中位置连续的牛来进行比赛。但是为了避免水平悬殊，牛们的身高不应该相差太大。

　　FJ准备了 \(Q\) 个可能的牛的选择和所有牛的身高 \(h_i\)，他想知道每一组里面最高和最低的牛的身高差别。

　　注意：在最大数据上，输入和输出将占用大部分时间。

【输入格式】

　　第 1 行：\(N\) 和 \(Q\)。
　　第 2 到第 \(N+1\) 行：第 \(i+1\) 行是第 \(i\) 头牛的身高。
　　第 \(N+2\) 到第 \(N+Q+1\)行：两个整数 \(A\) 和 \(B(1≤A≤B≤N)\)，表示从 \(A\) 到 \(B\) 的所有牛。

【输出格式】

　　输出包含 \(Q\) 行，两行输出每个可能的结果。

【输入输出样例1】

　Input

6 3
1
7
3
4
2
5
1 5
4 6
2 2

　Output

6
3
0

【数据限制】

　　对于 \(20\%\) 的数据，\(1≤N≤50000\)，\(1≤Q≤180000\)，\(1≤h_i≤10^9\)

【来源】

　　Mr.he