奇怪的老闆


提交答案

分數: 100 (部分)
時間限制: 1.0s
記憶體限制: 1G

作者:
題目類型

有一個很古怪的老闆,他有N名員工,每個人有自己的薪水

這個老闆很喜歡去找出編號第A到編號到B之間的最高薪水與最低薪水的差,但是你以為他只找一次嗎?

當然不是,他有強迫症,他每隔1秒就隨機寫兩個數字,然後找出這段數字裡最多薪水的錢,並寫下來作成紀錄。

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

輸入格式

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

接下來有 \(N\)行代表第\(1 \sim N\)名的員工薪水。

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

輸出格式

對於每一個問題,印出最高薪水與最低薪水的差為何?並換行。

範例輸入

6 3
1
7
3
4
2
5
1 5
4 6
2 2

範例輸出

6
3
0

留言

目前沒有評論。