测试数据来自 system/1467

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

---

【问题描述】

　　农夫约翰的 \(N\) 头奶牛，每天挤奶时总会按同样的顺序站好。一日，农夫约翰决定为奶牛们举行一个“终极飞盘”比赛。为简化问题，他将从奶牛队列中选出一个连续区间来进行游戏。不过，参加游戏的奶牛要玩的开心的话就不能在身高上差距太大。

　　农夫约翰制定了 \(Q\) 个预定的参赛组，给出它们的身高 (1 ≤ 身高 ≤ 1,000,000)。对每个参赛组，他需要你帮助确定组中最高牛和最低牛的身高差。

【输入格式】

　　第 \(1\) 行: 两个空格隔开的整数，\(N\) 和 \(Q\)。
　　第 \(2..N+1\) 行: 第 \(i+1\) 行包含一个整数表示第 \(i\) 头牛的身高，身高是 \(1..1000000\) 之间的整数。
　　第 \(N+2..N+Q+1\) 行: 两个整数 \(A\) 和 \(B(1 ≤ A ≤ B ≤ N)\)，表示一个从 \(A\) 到 \(B\) 的参赛组区间。

【输出格式】

　　第 \(1..Q\) 行: 每行包含一个整数来表示区间上最大身高差。

【输入输出样例】

　Input

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

　Output

6
3
0

【数据说明】

　　对于 \(100\%\) 的数据，\(1 ≤ N ≤ 50,000\)，\(1 ≤ Q ≤ 200,000\)

【来源】

　　Mr.he