No submission language available for this problem.

Background

Special for beginners, ^_^

Description

询问对于 n 个数中，指定 [L, R] 区间中的最大最小值的差值。

Format

Input

第一行两个整数 n，q 分别表示有 n 个整数和 q 次询问。

第二行开始的 n 行，每行一个整数，表示序列数

最后 q 行每行两个整数 L，R

Output

共 q 行输出，每行一个对应的 [L, R] 区间的最大最小差值。

Samples

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

6
3
0

Limitation

$1≤n≤5×10^4$

$1≤q≤1.8×10^5$

$1≤a_i≤10^6,1≤i≤n$

1s, 1024KiB for each test case.