每天挤奶时，Farmer John 的 $N$ 头奶牛（$1 \le N \le 50,000$）总是按相同的顺序排队。一天，Farmer John 决定组织一些奶牛玩极限飞盘。为了简单起见，他会从挤奶队列中选取一段连续的奶牛来参加游戏。不过，为了让所有奶牛都玩得开心，它们的身高不能相差太大。

Farmer John 列出了 $Q$（$1 \le Q \le 200,000$）组可能参加游戏的奶牛及其身高（$1 \le height \le 1,000,000$）。对于每组奶牛，他希望你帮助确定其中最高和最矮奶牛的身高差。

输入格式

从标准输入读取输入。

第 1 行：两个以空格分隔的整数 $N$ 和 $Q$。

第 $2 \ldots N+1$ 行：第 $i+1$ 行包含一个整数，表示第 $i$ 头奶牛的身高。

第 $N+2 \ldots N+Q+1$ 行：两个整数 $A$ 和 $B$（$1 \le A \le B \le N$），表示从 $A$ 到 $B$ 的奶牛范围，包含两端。

输出格式

将输出写入标准输出。

第 $1 \ldots Q$ 行：每行包含一个整数，回答相应询问，表示该范围中最高和最矮奶牛的身高差。

样例

输入格式 1

6 3
1
7
3
4
2
5
1 5
4 6
2 2

输出格式 1

6
3
0

题目来源：USACO 2007 年 1 月金组