每天农夫John的N（1≤N≤50000）头牛总是按同一序列排队。有一天，John决定让一些牛玩一场飞盘比赛。他准备找一群在队列中位置连续的牛来进行比赛，但是为了避免水平悬殊，牛的身高不应该相差太大。John准备了Q（1≤Q≤180000）个可能的牛的选择和所有牛的身高（1≤身高≤1000000）。他想知道每一组里面最高和最矮的牛的身高差别。注意：在最大数据上，输入和输出将占用大部分运行时间。

第一行：N和Q。

第2…N+1行：第i+1行是第i头牛的身高。

第N+2…N+Q+1行：两个整数A和B（1≤A≤B≤N），表示从A到B的所有牛。

第1…Q行：所有询问的回答（最高和最低的牛的身高差），每行一个。

一本通