Problem : 183 - 排隊

Problem Statistics

Solved Member: 32　　Submission: 112　　User Tried: 40

Statement:

Farmer John有N頭乳牛呈一字排開

每頭乳牛都有自己的身高

現在給Q筆詢問，每次查詢區間[a,b]，FJ想知道這段範圍內最高的牛和最矮的牛差距是多少

Input:Output:

每個測試檔僅有一筆測試資料
第一行有兩個正整數N,Q，意義如題敘(N≦50000,Q≦200000)
緊接著N行，每行有一正整數代表乳牛的高度(不超過1000000)
最後Q行，每行有兩個正整數a,b，代表要查詢區間[a,b](其中1≦a≦b≦N)

對於每一筆詢問，輸出一行非負整數代表區間最大值-區間最小值

Sample Input:Sample Output:

5 3
1
2
3
2
1
3 3
2 4
1 5

0
1
2

Source:

USACO 2007 January Gold

Problem Setter

lajisongyy_jack1

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	10
2	1000ms	65536kb	10
3	1000ms	65536kb	10
4	1000ms	65536kb	10
5	1000ms	65536kb	10
6	1000ms	65536kb	10
7	1000ms	65536kb	10
8	1000ms	65536kb	10
9	1500ms	65536kb	10
10	2000ms	65536kb	10