訓練1　區間最值差

題目描述（POJ3264）：每天擠奶時，約翰的N頭奶牛（1≤N≤50,000）都以相同的順序排隊。他挑選一系列連續的奶牛來玩游戲。為了讓所有奶牛都玩得開心，它們的高度差異不應太大。約翰列出了Q組（1≤Q≤200,000）奶牛和它們的高度（1≤height≤1,000,000）。他希望確定每個小組中最高和最矮的奶牛之間的高度差異。

輸入：第1行包含兩個整數N和Q。接下來N行，每行都包含一個整數，表示奶牛的高度。最后Q行，每行都包含兩個整數A和B（1≤A≤B≤N），代表從A到B的奶牛范圍。

輸出：輸出Q行，每行都包含一個整數，表示該范圍內最高和最矮奶牛的高度差。

題解：本題求解區間最大值和最小值之差，是典型的RMQ問題，可以使用ST解決。

1. 算法設計

（1）創建ST。

（2）查詢[a, b]區間的最大值和最小值，然后輸出其差值。

2. 算法實現