题目描述

有 $n$ 个数 $a_i$。

有 $q$ 次询问，每次询问给出两个数 $l$ 和 $r$ ，表示询问区间 $[l,r]$ 内最大值和最小值的差。

输入格式

第一行两个数 $n \ q \ (1\le n\le 5\times 10^4,1\le q\le 1.8\times10^5))$。

下来 $n$ 个数 $a_i\ (1\le a_i\le 10^6)$。

下来 $q$ 行，每行两个整数 $l \ r$。

输出格式

输出共 $q$ 行，对于每组询问输出一个整数，表示询问区间内最大值与最小值的差。

输入输出样例 #1

输入 #1

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

输出 #1

6
3
0