训练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. 算法实现