Farmer John 的 $N$ 头（$1 \le N \le 50,000$）奶牛每天挤奶都按相同顺序排队。一天他要和一些奶牛玩极限飞盘。为简单起见，选队列连续区间，但身高不能差太大才让所有牛玩得开心。
他列出 $Q$（$1 \le Q \le 200,000$）个候选组和牛的身高（$1 \le height \le 1,000,000$）。对每组求最高与最矮的身高差。
输入格式
从标准输入读取。
第 1 行：空格分隔整数 $N$、$Q$。
第 $2..N+1$ 行：第 $i+1$ 行为牛 $i$ 身高整数。
第 $N+2$..$N+Q+1$ 行：整数 $A$、$B$（$1 \le A \le B \le N$），表示 $A$ 到 $B$ 包含两端的区间。
输出格式
写入标准输出。
第 $1..Q$ 行：各一个整数，回答相应查询的区间最高与最矮身高差。
样例
输入格式 1
6 3 1 7 3 4 2 5 1 5 4 6 2 2
输出格式 1
6 3 0
题目来源：USACO 2007 年 1 月银组