You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

原题来自 USACO 2007 Jan. Gold

FJ 的 $N$ 头牛总是按同一序列排队。有一天，FJ 决定让一些牛玩一场飞盘比赛。他准备找一群在对列中为置连续的牛来进行比赛，但是为了避免水平悬殊，牛的身高不应该相差太大。FJ 准备了 $Q$ 个可能的牛的选择和所有牛的身高。他想知道每一组里面最高和最低的牛的身高差别。

输入格式

第一行：$N$ 和 $Q$；
第二至第 $N+1$ 行，第 $i+1$ 行是第 $i$ 头牛的身高 $h_i$；
第 $N+2$ 至第 $N+Q+1$ 行，每行两个整数 $A$ 和 $B$，表示从 $A$ 到 $B$ 的所有牛。

输出格式

第一至第 $Q$ 行，每行一个整数，表示对于询问的回答（即最高和最低的牛的身高差）。

样例

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

6
3
0

数据范围与提示

对于全部数据，$1\le N\le 5\times 10^4,1\le Q\le 1.8\times 10^5,1\le h_i\le 10^6,1\le A\le B\le N$。