说明

求区间最接近且不相等的两数之差的绝对值。

注：最接近指数值上最接近

输入格式

第一行输入两个整数 $N,Q$，分别代表序列的长度和询问的个数。

第二行包含 $N$ 个由一个空格分开的正整数，代表了整个序列，从左向右依次编号为 $A_1, A_2……A_n$。

接下来 $Q$ 行，每行两个整数 $i,j$ 表示了一个询问区间。

输入数据保证 $1\le i<j\le N$。

输出格式

对于每一个询问输出一行，为所问区间中最接近两个数之差的绝对值。

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

2
4
1

提示

对于 $100\%$ 的数据，$1\le N,Q\le10^5,1\le A_i\le10^9$。

数据为全部纯随机生成。