TopCoder

User's AC Ratio

41.7% (10/24)

Submission's AC Ratio

15.2% (22/145)

Tags

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

5
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

2
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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 2
6 1000 65536 262144 2
7 1000 65536 262144 2
8 1000 65536 262144 2
9 1000 65536 262144 2