Farmer John の $N$ 頭（$1 \le N \le 50,000$）は毎日同順序で搾乳に並びます。ある日一部でアルティメットをします。簡単にするため連続区間を選びますが、皆が楽しむには身長差が大きすぎてはいけません。

$Q$（$1 \le Q \le 200,000$）候補グループと身長（$1 \le height \le 1,000,000$）のリストから、各組の最高と最低の差を求めます。

入力

標準入力から読んでください。

第 1 行：空白区切り整数 $N$、$Q$。

第 $2..N+1$ 行：第 $i+1$ 行は牛 $i$ の身長整数。

第 $N+2$..$N+Q+1$ 行：整数 $A$、$B$（$1 \le A \le B \le N$）、両端込み $A$〜$B$。

出力

標準出力へ書いてください。

第 $1..Q$ 行：各一整数、質問区間の最高と最低の差。

入出力例

入力 1

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

出力 1

6
3
0

出典：USACO 2007 年 1 月シルバー