Rebrending

题意翻译

一个 $n$ 个数的序列，$q$ 次询问。每次问区间 $[l,r]$ 中选择两个数，他们的差的绝对值最小是多少。

题目描述

Kostya and Zhenya — the creators of the band "Paper" — after the release of the legendary album decided to create a new band "Day movers", for this they need to find two new people. They invited $ n $ people to the casting. The casting will last $ q $ days. On the $ i $ th of the days, Kostya and Zhenya want to find two people on the segment from $ l_i $ to $ r_i $ who are most suitable for their band. Since "Day movers" are doing a modern art, musical skills are not important to them and they look only at other signs: they want the height difference between two people to be as small as possible. Help them, and for each day, find the minimum difference in the growth of people from the casting on this segment!

输入输出格式

输入格式

In the first line you are given two integers $ n $ and $ q $ ( $ 2 \leq n \leq 3 \cdot 10^5, 1 \leq q \leq 10^6 $ ) — the number of people who came to the casting and the number of casting days. In the second line, you are given $ n $ integers $ a_1, a_2, a_3, \ldots, a_n $ ( $ 1 \leq a_i \leq n $ ) — the growth of each of the candidates. It is also guaranteed that all $ a_i $ are different. The following $ q $ lines each contains two integers $ l_i $ and $ r_i $ ( $ 1 \leq l_i < r_i \leq n $ ) — a segment of people on the $ i $ th day of casting.

输出格式

Output $ q $ lines. In the $ i $ -th line there should be a minimum height difference between the two candidates on the segment on the $ i $ -th day of casting.

输入输出样例

输入样例 #1

3 3
1 3 2
1 2
2 3
1 3

输出样例 #1

2
1
1

输入样例 #2

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

输出样例 #2

3
2
2

输入样例 #3

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

输出样例 #3

2
4
2
1

说明

In the first example, the minimum difference on the segment $ [1, 2] $ is $ 2 $ , on the segment $ [2, 3] $ — $ 1 $ , on the segment $ [1, 3] $ is also $ 1 $ . In the third example, the numbers with the minimum difference on the segment $ [4, 6] $ are $ 3 $ and $ 5 $ ( $ 5 - 3 = 2 $ ). On the segment $ [1, 2] $ , the numbers with the minimum difference are $ 2 $ and $ 6 $ ( $ 6 - 2 = 4 $ ). On the segment $ [3, 6] $ , the numbers with the minimum difference are $ 1 $ and $ 3 $ ( $ 3 - 1 = 2 $ ). On the segment $ [1, 3] $ , the minimum difference is formed by the numbers $ 1 $ and $ 2 $ ( $ 2 - 1 = 1 $ ).