题目描述

每天，农夫约翰的 N 头奶牛总是按同一顺序排好队，有一天，约翰决定让一些牛玩一场飞盘游戏，他决定在队列里选择一群位置连续的奶牛进行比赛，为了避免比赛结果过于悬殊，要求挑出的奶牛身高不要相差太大。 约翰准备了 Q 组奶牛选择，并告诉你所有奶牛的身高 $H_i$。他想知道每组里最高的奶牛和最矮的奶牛身高差是多少。 注意：在最大的数据上，输入输出将占据大部分时间。

输入格式

第一行，两个用空格隔开的整数 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 1
1
1 1

0

25 40
89
362
335
16
78
440
37
31
354
252
493
370
440
85
394
264
205
106
315
441
471
80
293
187
445
1 25
1 1
25 25
17 25
1 5
4 6
8 14
8 22
10 17
15 17
9 16
7 7
5 12
14 23
10 25
4 11
2 15
1 12
22 23
1 21
1 24
6 24
13 21
15 25
9 22
15 23
10 12
3 4
1 3
1 19
3 4
2 17
13 17
4 21
1 23
7 9
3 24
11 21
3 6
7 11

477
0
0
391
346
424
462
462
408
189
408
0
462
391
413
477
477
477
213
477
477
462
386
391
413
391
241
319
273
477
319
477
355
477
477
323
477
408
424
462

提示

数据范围

对于50%的数据，$1\le N\le 1000, 1\le Q\le 2000$。 对于另外10%的数据，$1\le Q\le 300$。 对于100%的数据，$1\le N\le 50000, 1\le Q\le 100000, 1\le H_i\le 10^{6}$。

（$1\le A\le B\le N$）