5913: 进阶2.1.1 区间最值差-1
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：97
解决：46
题目描述
在每天挤奶的时候，农民约翰的N头牛（1≤n≤50000）总是排成一列。
有一天，约翰决定与他的牛们一起玩一个极限飞盘游戏。为了简单起见，他将从奶牛队列里面选一定范围内的奶牛来玩这个游戏，然而所有的牛对这个游戏都很感兴趣。
农民约翰列出了Q份名单（1≤Q≤200 000）和每个奶牛的高度（1≤高度≤1 000 000）。对于每一份名单，他想你帮助他确定在每份名单中高度最高的奶牛与高度最低的奶牛的高度差是多少。
有一天，约翰决定与他的牛们一起玩一个极限飞盘游戏。为了简单起见，他将从奶牛队列里面选一定范围内的奶牛来玩这个游戏，然而所有的牛对这个游戏都很感兴趣。
农民约翰列出了Q份名单（1≤Q≤200 000）和每个奶牛的高度（1≤高度≤1 000 000）。对于每一份名单，他想你帮助他确定在每份名单中高度最高的奶牛与高度最低的奶牛的高度差是多少。
输入
第一行为N(1≤N≤50000)和Q(1≤Q≤200000)
从第2行到第N+1行，每行一个数字，表示第i头牛的高度(1≤height≤1000000)
从第N+2行到第N+Q+1行，每行两个整数A和B(1≤A≤B≤N)，表示求从第A头牛到第B头牛的最值差
从第2行到第N+1行，每行一个数字，表示第i头牛的高度(1≤height≤1000000)
从第N+2行到第N+Q+1行，每行两个整数A和B(1≤A≤B≤N)，表示求从第A头牛到第B头牛的最值差
输出
从第一行到第Q行，每行一个整数，表示从第A头牛到第B头牛之间，最高牛与最矮牛的高度差
样例输入 复制
6 3
1
7
3
4
2
5
1 5
4 6
2 2样例输出 复制
6
3
0