User's AC Ratio

92.9% (92/99)

Submission's AC Ratio

39.3% (267/679)

Tags

Description

2010年的USACO牛力大賽,神人們齊聚一堂,打算要一較高下,看誰最

地主隊是由John帶領的乳牛們,可惜在第一回合預賽就被暖身的surwdkgo給刷掉了。

接下來的大戰可就精彩了,表演了解決氾濫黃河的書泓,幫忙愚公移山而以龐大能量炸掉聖母峰的ATP,降下滂沱大雨解決埃及乾旱的水……等等,這些大牛的卓越表現直逼去年冠軍乃牛
經過3天2夜的激戰,令人期待不已的成績終於出來了。

如鬼魅一般神出鬼沒,輕鬆就嚇爆裁判的小鬼奪得第2。而第1則被擁有七十二變的蚯蚓一哥奪得。被電得滾來滾去的小可魚則被好威shik獲頒時嗣鳴特別獎

這天,第一神牛蚯蚓來到了一個相當前衛的都市,麻煩難懂的波蘭都市,這個都市的人們都非常喜歡波蘭文化,學校的教材都以POI為樣板打造,相當有深度。

只可惜蚯蚓享譽盛名的時光並不長久,可憐的蚯蚓在被忌妒的歹徒殺害後,被分屍在這個城市的某條街道上,但本能的擬態,讓他的屍身模擬成這個城市的高樓大廈。

經過好威書泓翻遍圖書館找到的結果,發現只要將蚯蚓的屍身重新找回來就能讓它復活,可惜蚯蚓的擬態會讓他盡可能的和周圍景觀不會太突兀,所以我們收集到這條街道上的高樓高度,但是實際上還是得經過一番分析,才有辦法找出哪些高樓是蚯蚓的屍身。

為了有效率的分析問題,我們需要快速的得到某兩個建築區間的最高大廈和最低大廈的高度差,希望你能寫一個程式解決這個問題。

你可以假設這條街道上的大廈是排成一直線的。

Input Format

每個測資檔只有單筆測資。

第一行有兩個整數n, m,分別代表有n棟大樓和m筆詢問。( 1≦n≦10 5 , 1≦m≦105)

第二行有n個整數Hi,代表街道上由左到右第 i 棟建築(編號為 i )的高度 (1≦Hi≦231)

第三行開始有m行,各有1組數字i, j,請找出第i棟大廈到第j棟大廈的之間(含)最高和最低的高樓大廈高度差。

Output Format

對於每個詢問,輸出一行包含1個整數代表詢問的答案。

Sample Input

8 3
5 7 3 1 9 7 10 11
1 5
1 8
6 8

Sample Output

8
10
4

Hints

Problem Source

原TIOJ1603 / Problem Setter: yuscvscv

Subtasks

For Testdata: 0 ~ 0, Score: 33
For Testdata: 1 ~ 1, Score: 33
For Testdata: 2 ~ 2, Score: 34
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144