Description

每天挤奶时，约翰的$N$ 头奶牛$（1≤N≤50,000）$都以相同的顺序排队。他挑选一系列连续的奶牛来玩游戏。为了让所有奶牛都玩得开心，它们的高度差异不应太大。约翰列出了$Q$组$（1≤Q ≤200,000）$奶牛和它们的高度$（1≤height≤1,000,000）$。他希望确定每个小组中最高和最矮的奶牛之间的高度差异。

Input

第$1$行包含两个整数$N$ 和$Q$ 。接下来$N$ 行，每行都包含一个整数，表示奶牛的高度。最后$Q$ 行，每行都包含两个整数$A$ 和$B （1≤A≤B ≤N ）$，代表从$A$ 到$B$ 的奶牛范围。

Output

输出$Q$ 行，每行都包含一个整数，表示该范围内最高和最矮奶牛的高度差。

Samples

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

6
3
0

来源

POJ3264