效率至上

Time Limit: 5000 ms Memory Limit: 65536 KiB

Problem Description

题意很简单,给出一个数目为n的非有序序列,然后有m次查询.对于每次查询输入两个正整数l,r请输出区间[l,r]的最大值与最小值的差值

Input

 第一行:输入两个正整数n,m    (1<=n<=50000,  1<=m<=200000  )

第二行:输入n个整数  大小范围为[1,100000];

接下来的m,每次两个正整数l,r (1<=l<=r<=n);

Output

 输出区间[l,r]最大值与最小值的差值.

Sample Input

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

Sample Output

6
3
0

Hint

 

Source