Background

Special for beginners, ^_^

Description

给出一个数列，$Q$ 次询问，每次给一对 $l,r$，询问 $a_l,\ldots, a_r$ 中 $|a_x-a_y|$（$a_x\ne a_y$）的最小值。

Format

Input

输入数据首先输入两个整数N,Q，分别代表序列的长度和询问的个数。这两个数字将单独占据一行并用一个空格分开。输入数据的第二行包含了N个由一个空格分开的正整数，代表了整个序列，从左向右依次编号为A1, A2……An。接下来Q行，每行两个整数i,j表示了一个询问区间。输入数据保证1≤i <j<=N

Output

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

Samples

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

2
4
1

Limitation

【数据规模和约定】 100%的数据中N≤100000，Q≤100000； 数据为全部纯随机生成。