Description

每天挤奶时，约翰的$N$ 头奶牛都以相同的顺序排队。

他挑选一系列连续的奶牛来玩游戏。为了让所有奶牛都玩得开心，它们的高度差异不应太大。

约翰列出了$Q$ 组奶牛和它们的高度 $height$。他希望确定每个小组中最高和最矮的奶牛之间的高度差异。

Format

Input

第$1$行包含两个整数$N$ 和$Q$ 。

接下来$N$ 行，每行都包含一个整数，表示奶牛的高度。

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

数据范围：$1≤N≤50000,1≤Q ≤200000,1≤height≤1000000。$

Output

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

Samples

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

6
3
0

来源

POJ3264