题目描述

对于每天的挤奶工作， Farmer John 的 N 头奶牛（$1 \leq N \leq 50,000$）总是按相同的顺序排队。有一天，Farmer John 决定组织一些奶牛玩极限飞盘游戏。为了简化问题，他会从挤奶队列中选取一个连续的奶牛区间来参与游戏。然而，为了让所有奶牛都能玩得开心，它们的身高差异不能太大。

Farmer John 列出了 Q 个（$1 \leq Q \leq 200,000$）可能的奶牛组及其身高（$1 \leq \text{身高} \leq 1,000,000$）。对于每个组，他希望你帮忙求出该组中最高奶牛和最矮奶牛的身高差。

输入格式

• 第 1 行：两个用空格分隔的整数 $N$ 和 $Q$。
• 第 2 到 $N+1$ 行：第 $i+1$ 行包含一个整数，表示第 $i$ 头奶牛的身高。
• 第 $N+2$ 到 $N+Q+1$ 行：两个整数 $A$ 和 $B$（$1 \leq A \leq B \leq N$），表示从第 $A$ 头到第 $B$ 头奶牛的区间。

输出格式

• 第 1 到 $Q$ 行：每行包含一个整数，对应每个查询的结果，即该区间内最高奶牛与最矮奶牛的身高差。

输入样例 1

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

输出样例 1

6  
3  
0  

题目来源

USACO 2007 年 1 月银牌赛