Migrated from Lutece 1591 An easy problem A

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

N个数排成一列，Q个询问，每次询问一段区间内的数的极差是多少。

Input

第一行两个整数N(1≤N≤50000),Q(1≤Q≤200000)。接下来一行N个整数a1 a2 a3 ....an,(1≤ai≤1000000000)。接下来Q行，每行两个整数L,R(1≤L≤R≤N)。

Output

对于每个询问输出一行，一个整数表示区间内的极差。

Samples

5 3
3 2 7 9 10
1 5
2 3
3 5

8
5
3

Resources

数据结构