题目描述

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

输入格式

第一行，两个用空格隔开的整数 N 和 Q。 第二到第 N+1 行，每行一个整数，第 i+1 行表示第 i 头奶牛的身高 $H_i$。 第 N+2 到第 N+Q+1 行，每行两个用空格隔开的整数 A 和 B，表示选择从 A 到 B 的所有牛（$1\le A\le B\le N$）。

输出格式

共 Q 行，每行一个整数，代表每个询问的答案。

样例输入

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

样例输出

6
3
0

提示

对于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 1
1
1 1

0

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

6
3
0

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

6
3
0