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 $ ).

**题目大意：**
一个包含 $ n $ 个数字的序列，和 $ q $ 次询问。每次询问一个区间 $[l, r]$ 中选择两个数字，使得这两个数字的差的绝对值最小。

**输入输出数据格式：**
- **输入格式：**
- 第一行：两个整数 $ n $ 和 $ q $，分别表示参加选拔的人数和选拔的天数。$(2 \leq n \leq 3 \times 10^5, 1 \leq q \leq 10^6)$
- 第二行：$ n $ 个整数 $ a_1, a_2, a_3, \ldots, a_n $，表示每个候选人的身高。$(1 \leq a_i \leq n)$，且所有 $ a_i $ 都互不相同。
- 接下来 $ q $ 行：每行两个整数 $ l_i $ 和 $ r_i $，表示第 $ i $ 天选拔的区间。$(1 \leq l_i < r_i \leq n)$
- **输出格式：**
- 输出 $ q $ 行，每行一个整数，表示第 $ i $ 天选拔区间内两人身高最小差值。**题目大意：** 一个包含 $ n $ 个数字的序列，和 $ q $ 次询问。每次询问一个区间 $[l, r]$ 中选择两个数字，使得这两个数字的差的绝对值最小。 **输入输出数据格式：** - **输入格式：** - 第一行：两个整数 $ n $ 和 $ q $，分别表示参加选拔的人数和选拔的天数。$(2 \leq n \leq 3 \times 10^5, 1 \leq q \leq 10^6)$ - 第二行：$ n $ 个整数 $ a_1, a_2, a_3, \ldots, a_n $，表示每个候选人的身高。$(1 \leq a_i \leq n)$，且所有 $ a_i $ 都互不相同。 - 接下来 $ q $ 行：每行两个整数 $ l_i $ 和 $ r_i $，表示第 $ i $ 天选拔的区间。$(1 \leq l_i < r_i \leq n)$ - **输出格式：** - 输出 $ q $ 行，每行一个整数，表示第 $ i $ 天选拔区间内两人身高最小差值。