题目描述
每天,农夫 John 的N头牛总是按同一序列排队。 有一天， John 决定让一些牛玩一场飞盘比赛。 他准备找一群在队伍中位置连续的牛来进行比赛。但是为了避免身高造成的水平悬殊，牛的身高不应该相差太大。 John 准备了Q 个可能的牛的选择和所有牛的身高。 他想知道每一组里面最高和最低的牛的身高差别。
输入
第1行：两个用空格隔开的整数N和Q。
第2~N+1行：每行包含1个整数，第i+1行的整数表示的是第i头牛的身高。
第N+2~N+Q+1行，每行包含两个整数A和B，表示从A到B的所有牛。
输出
有Q行，每行1个整数，表示最高和最矮的牛的身高差。
6 3
1
7
3
4
2
5
1 5
4 6
2 2
提示
对于100%的数据，有1≤N≤50000，1≤Q≤180000，1≤牛的身高≤1000000，1≤A≤B≤N。