a041: 奇怪的老闆
Tags :
Accepted rate : 13人/28人 ( 46% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-11-25 13:32

Content

有一個很古怪的老闆,他有N名員工,每個人有自己的薪水,這個老闆很喜歡去找出編號第A到編號到B之間的最高薪水與最低薪水的差,但是你以為他只找一次嗎?當然不是,他有強迫症,他每隔1秒就隨機寫兩個數字,然後找出這段數字裡最多薪水的錢,並寫下來作成紀錄。

老闆每次都要他的秘書幫他找,他的秘書受不了,想請你幫她寫一個程式讓他可以很迅速的找到,在這區間最高薪水與最低薪水的差是多少錢, 好讓他可以輕鬆一下。

Input

第一行有兩個數字N(1 ≤ N ≤ 50,000), Q (1 ≤ Q ≤ 200,000) 代表有N名員工跟Q個問題。

接下來有 N行代表第1~N名的員工薪水。

在接下來的Q行有兩個數字 a,b(0<a<=b<=n)代表老闆寫的兩個數字,請你找出這段區間的最高薪水與最低薪水的差。

Output
對於每一個問題,印出最高薪水與最低薪水的差為何?並換行。
Sample Input
6 3
1
7
3
4
2
5
1 5
4 6
2 2
Sample Output
6
3
0
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (30%): 1.0s , <1M
公開 測資點#4 (30%): 1.0s , <10M
Hint :
Tags:
出處:
[管理者:
zero (管理員)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」