獨行玩家

題目敘述

攻略組以攻略艾恩葛朗特為目標，由數百位頂尖玩家所組成。

你，黑衣劍士，是在最前線戰鬥的攻略組一員，身為獨行玩家的你總是得隻身一人對抗敵人。

然而，有時也難免會有寡不敵眾、陷入苦戰的時候，這時就得隨時確認自己的安危，以免一不小心就被登出；作為經驗豐富的封弊者，再加上索敵技能點滿，你總是可以清楚知道範圍內所有敵人的戰鬥力，當你感覺到危險的時候，你會待在戰鬥力最低的敵人旁，這時你用來評估當前危險的程度，就是看戰鬥力最高的敵人與你(或者說戰鬥力最低的敵人)距離有多遠，太近的話，那可能就得趕快用水晶傳送走了。

為了簡化問題，假定有$N$個敵人，且他們分別在座標$1,2,3...N$的位置，而他們分別的戰鬥力為$A_1,A_2,A_3...A_N$。你會多次評估當前範圍危險的程度。

而你索敵技能已經點滿了，所以每次索敵的範圍固然都是相同的。

輸入說明

第一行有兩個整數$N(1\leq N\leq 5000)$和$Q(1\leq Q\leq 10^6)$，表示敵人的數量與評估的次數。

第二行有$N$個整數$A_1,A_2,A_3...A_N(1\leq A_i\leq N$且所有的$A_i$皆不相等$)$，表示各個敵人的戰鬥力。

接下來$Q$行，每行有兩個整數$l,r(1\leq l\leq r\leq N$且所有的$r-l$皆相等$)$，表示評估的範圍是$[l,r]$。

輸出說明

對於每次評估，輸出戰鬥力最高與最低的兩個敵人的距離，並換行。

範例輸入

20 5
20 8 18 12 7 14 19 9 6 13 5 10 17 3 16 2 11 4 1 15
3 11
1 9
7 15
12 20
10 18

範例輸出

子任務

子任務一($87\%$)：$Q\leq 5000$
子任務二($13\%$)：無限制

提示

化成題目我也認得

Judge Setting

run-time limit: 2000 ms
memory limit: 538443776 byte
測資數量: 10