1905 . 最理想的身高差
Description
如果你常常看某些日本插畫家的Twitter的話，也許你會看到一些萌萌的圖片，像是這張：
這張圖雖然看起來很美好，但事實上，女生可能因為看不見你看的見的東西而讓他想到身高憤而咬你打你（ 還是很美好
有著大量身高差的情侶乍看之下好像很萌，實際上卻常常會有一些麻煩的地方，比如接吻的時候要彎腰或是蹲下，很不方便（ 這就叫身在福中不知福
比如下面這張圖：
我們可以看到，如果男方身高太高，可能會遭受各種非人道的對待（ 真是太幸福了
當然，身高差也不一定不好啦！
像是下面這張圖應該是個很好的反例：
我好像長太高了QAQ
嘛～不過我們還是先專注在身高差越小越好的狀況吧?!
現在假設你不小心駭入了校務系統拿到了全學年同學的身高資料(依照學號排序)。
接下來馬上就要分班了，雖然不知道實際分班狀況，但是你很確定連續的學號一定會分在同一班。
同一個班裡面，每個人的身高有高有矮，一定有一對同學，身高差距是全班裡面所有配對中最小的！
如果事先找出這對同學，那你就能夠暗中幫助他們牽線搭橋，他們一定會很感謝你！
嘛～可是你還不確定分班狀況，所以你決定先寫一個程式，讓你輸入一個班級（你不知道到時候會怎麼分，所以你用一個左界跟右界代表一個班級），馬上幫你找出那個班上最理想的身高差是多少！（ 為什麼看起來身高差根本就是好東西
Input Format
第一行有一個整數 $N$ ，代表整學年總共有幾個同學。
第二行有 $N$ 個無號32位元整數，代表同學的身高（身高是0應該也不是件奇怪的事吧?!）
第三行有一個整數 $Q$ 代表你想要做的查詢。
接下來 $Q$ 行，每行有兩個整數 $Ai, Bi$，代表你想要查詢的班級，其中這兩個整數分別代表班級的左界和右界。
30% ， $ 1 \leq N,Q \leq 10^ 3$
100%， $ 1 \leq N,Q \leq 10^ 5 ; 1 \leq Ai < Bi \leq N$
Output Format
對於每個你的詢問，輸出一行，包含一個整數，代表該班級中最小的身高差。
Sample Input 1
4 2 5 3 1
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
Sample Output 1
1
1
1
3
1
1
2
2
2
Hints
诶～你說你突然想到了性別的問題？
別傻了好嗎XD
全校都是男生會有什麼問題啊～（疑!!!!!!!!
Problem Source
題目：johnchen902
測資：多多
敘述：果茶
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 30 |
| 2 | 5~9 | 70 |