每天擠奶時，Farmer John 的 $N$ 頭奶牛（$1 \le N \le 50,000$）總是按相同的順序排隊。一天，Farmer John 決定組織一些奶牛玩極限飛盤。為了簡單起見，他會從擠奶隊列中選取一段連續的奶牛來參加遊戲。不過，為了讓所有奶牛都玩得開心，牠們的身高不能相差太大。

Farmer John 列出了 $Q$（$1 \le Q \le 200,000$）組可能參加遊戲的奶牛及其身高（$1 \le height \le 1,000,000$）。對於每組奶牛，他希望你幫忙確定其中最高和最矮奶牛的身高差。

輸入格式

從標準輸入讀取輸入。

第 1 行：兩個以空格分隔的整數 $N$ 和 $Q$。

第 $2 \ldots N+1$ 行：第 $i+1$ 行包含一個整數，表示第 $i$ 頭奶牛的身高。

第 $N+2 \ldots N+Q+1$ 行：兩個整數 $A$ 和 $B$（$1 \le A \le B \le N$），表示從 $A$ 到 $B$ 的奶牛範圍，包含兩端。

輸出格式

將輸出寫入標準輸出。

第 $1 \ldots Q$ 行：每行包含一個整數，回答對應詢問，表示該範圍中最高和最矮奶牛的身高差。

範例

輸入格式 1

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

輸出格式 1

6
3
0

題目來源：USACO 2007 年 1 月金組