百柒級熊寶貝是眾所皆知的臺大資工電神，他喜歡帶著他的Surface到處電人。
而他現在正忙著在氣球盃中電人，但是他卻解不出來pC。
為了舒緩壓力，他離開了座位，先去教別人要怎麼把指考化學考到100分。
接著再到教室外面吃披薩和喝飲料。
打開筆電看了一集JoJo。
又跟脖子等人一起打了幾場風聲。
然後又去吃了一餐品苑。
最後為了減肥，瞬間移動到臺大參加5公里的馬拉松，結果因為晶片沒讀到而完成時間從31'變成了46'47"。而聰明的他推論出：這是一定是替身攻擊！。
雖然熊寶貝在這兩小時內過得很充實，但是他還是要面對現實。請你幫他解決他卡了很久的這題。

Input

問題很簡單：
給一長度為\(n\)的陣列，請且詢問\(q\)次。
對於每次查詢，找到子區間的\(max({a_i-a_j})\)(\(l \leq j \lt i \leq r\), 其中 \(l,r\)為子區間的左、右界線)

第一行包含兩個數字，分別是\(n\)和\(q\)。
第二行有\(n\)個數字，分別代表\(a_1, a_2, a_3 ... a_n\)。 接下來有\(q\)行，分別是\(l, r\)，代表查詢子區間的左、右界線(含) 。

Output

總共有\(q\)行，請輸出每次查詢的\(max({a_i-a_j})\)(\(l \leq j \lt i \leq r)\)

Constraints

第 \(1\) 組測資, \(n\leq10^2\), \(q=1\)。 \((35\text{%})\)

第 \(2\) 組測資, \(n\leq10^2\)。 \((25\text{%})\)

第 \(3\) 組測資, \(n\leq10^4\)。 \((15\text{%})\)

第 \(4\) 組測資, \(n\leq2*10^5\)。\((25\text{%})\)

對於所有測資，\(1 \leq q \leq n\), \(0 \leq a_i \leq 10^6\), \(1\leq l < r \leq n\)。

Sample Input

10 4
1 2 6 4 3 7 8 9 0 10
1 6
2 9
3 7
5 6

Sample Output

6
7
5
4