原題來自 USACO 2007 Jan. Gold

FJ 的 N 頭?？偸前赐恍蛄信抨?duì)。有一天，F(xiàn)J 決定讓一些牛玩一場飛盤比賽。他準(zhǔn)備找一群在對列中為置連續(xù)的牛來進(jìn)行比賽，但是為了避免水平懸殊，牛的身高不應(yīng)該相差太大。FJ 準(zhǔn)備了 Q 個(gè)可能的牛的選擇和所有牛的身高。他想知道每一組里面最高和最低的牛的身高差別。

第一行：N 和 Q；

第二至第 N+1 行，第 i+1 行是第 i 頭牛的身高 h_i ；

第 N+2 至第 N+Q+1 行，每行兩個(gè)整數(shù) A 和 B，表示從 A 到 B 的所有牛。

第一至第 Q 行，每行一個(gè)整數(shù)，表示對于詢問的回答（即最高和最低的牛的身高差）。

數(shù)據(jù)范圍與提示：

對于全部數(shù)據(jù)，1≤N≤5×10⁴,1≤Q≤1.8×10⁵,1≤h_i≤10⁶,1≤A≤B≤N。

信息學(xué)一本通 數(shù)據(jù)結(jié)構(gòu)