Migrated from Lutece 3146 你们都是我的翅膀

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

QHJ同学最近对航模特别感兴趣，他打算亲自动手组装自己的航模。现在，他的航模除了机翼以外的部分已经装配完成了。

他咨询了一家航模配件店，这家航模配件店共有 $n$ 个不同的机翼，编号从 $1$ 到 $n$ ，编号为 $i$ 的机翼长度为 $a_i$ 。然而，所有机翼长度 $a_i$ 构成了一个排列，这意味着从 $1$ 到 $n$ 的每一个整数都恰好出现了一次，所以，QHJ同学没有办法在这家店找到两个长度相同的机翼。

没有办法，为了尽可能让航模可以飞行，QHJ同学只好选择长度差距尽可能小的两个机翼来安装到他的航模上。定义选择编号为 $i, j$ 的两种机翼给航模带来的不稳定度为 $| a_i-a_j |$ ，QHJ同学需要让航模的不稳定度尽可能小。你能帮助QHJ同学解决这个问题吗？

QHJ同学共发起了 $q$ 次询问，对于每一次询问，老板会向他展示编号在 $[L, R]$ 区间中的所有机翼。请你帮助确定，如果QHJ在这个区间中选择两个机翼，则航模的不稳定度最小是多少？

Input

第一行两个整数 $n$ 和 $q$ ，表示机翼的数量和询问的数量。 第二行有 $n$ 个整数 $a_1, a_2, ..., a_n$ ，表示编号从 $1$ 到 $n$ 的机翼的长度。 接下来共有 $q$ 行，每行两个整数 $L_i, R_i$ ，表示询问的区间。

Output

输出 $q$ 行，每行代表第 $i$ 次询问的答案。

Samples

3 3
1 3 2
1 2
2 3
1 3

2
1
1

5 3
4 1 5 3 2
1 2
3 4
2 4

3
2
2

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

2
4
2
1

Constraints

$2 \leq n \leq 3 \times 10^5，1 \leq q \leq 10^6，1 \leq L_i < R_i \leq n$ ， 保证 $a_1, a_2, ..., a_n$ 构成 $1$ 到 $n$ 的一个排列。