5959: 进阶2.5.3 区间最值差-2
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：93
解决：30
题目描述
每天挤奶时，约翰的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的奶牛范围。
接下来N行，每行都包含一个整数，表示奶牛的高度。
最后Q行，每行都包含两个整数A和B(1≤A≤B≤N),代表从A到B的奶牛范围。
输出
输出Q行，每行都包含一个整数，表示该范围内最高和最矮奶牛的高度差。
样例输入 复制
6 3
1
7
3
4
2
5
1 5
4 6
2 2样例输出 复制
6
3
0