[Usaco2007 Jan]Balanced Lineup

每天挤奶时，农夫 John 的 $N$ 头牛总是按照相同的顺序排队。

一天，John 决定挑选一些牛参加飞盘比赛。为了便于组织，他会从挤奶队伍中选择一段位置连续的牛。为了让所有牛都能愉快地参加比赛，这些牛的身高不能相差太大。

John 记录了每头牛的身高，并准备了 $Q$ 个候选区间。对于每个区间，请求出其中最高的牛与最矮的牛之间的身高差。

注意：在最大规模的数据中，输入和输出可能占用较多时间。

输入格式

第一行包含两个以空格分隔的整数 $N$ 和 $Q$，分别表示牛的数量和询问数量。

接下来 $N$ 行，第 $i$ 行包含一个整数 $h_i$，表示第 $i$ 头牛的身高。

接下来 $Q$ 行，每行包含两个整数 $A$ 和 $B$，表示询问队伍中从第 $A$ 头牛到第 $B$ 头牛的连续区间，包括两端。

输出格式

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个询问区间内最高的牛与最矮的牛之间的身高差。

样例输入

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 2\times 10^5$；
• $1\le h_i\le 10^6$；
• 对于每个询问，$1\le A\le B\le N$。

来源与许可

本题为 USACO 2007 January 试题「Balanced Lineup」，题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

6
3
0