[Jsoi2009]面试的考验

给定一个长度为 $N$ 的正整数序列 $A$，以及 $Q$ 个区间询问。

对于每个询问区间 $[i,j]$，需要在该区间内选择两个数值不同的元素，求它们之差的绝对值的最小值，即区间内元素的最小正差。若区间内所有元素的数值均相同，则答案为 $0$。

输入格式

第一行包含两个整数 $N,Q$，分别表示序列长度和询问个数。

第二行包含 $N$ 个由空格分隔的正整数 $A_1,A_2,\ldots,A_N$，表示给定序列。

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

评测数据中的序列随机生成，每个 $A_i$ 均独立且等概率地取自 $[1,10^9]$。

输出格式

对于每个询问，输出一行一个整数，表示区间 $[i,j]$ 内两个不同数值之差的绝对值的最小值。

若区间内所有元素的数值均相同，则输出 $0$。

样例输入

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

样例输出

2
4
1

数据范围

• $1\le N,Q\le 10^5$；
• $1\le A_i\le 10^9$；
• $1\le i<j\le N$；
• 每个 $A_i$ 独立且等概率地取自 $[1,10^9]$。

来源与许可

本题为 JSOI 2009 试题「面试的考验」，题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

2
4
1