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 月銀組