J3 实践-8 最大最小值

题目描述

对于每日挤奶，$\text {Farmer John}$ 的 $N$ 头奶牛总是以相同的顺序排列。有一天，农夫约翰决定与一些奶牛组织一场终极飞盘游戏。为简单起见，他将从挤奶阵容中选取一系列连续的奶牛来玩游戏。然而，为了让所有的奶牛都玩得开心，它们的高度不应该相差太大。 $\text{Farmer John}$ 列出了 $Q$ 个潜在奶牛组及其高度 。对于每组，他希望您帮助确定该组中最矮和最高的母牛之间的高度差异。

输入格式

第一行：两个空间分开的整数，$N$和$Q$。 第 $2 \sim N +1$ 行：第$i +1$ 行包含一个整数，即奶牛$i$ 的高度 第$N+2 \sim N + Q +1$ 行：两个整数A和B（$1 \le A \le B \le N$），代表从A到B的奶牛范围。

输出格式

第 $1...Q$ 行：每行包含一个整数，它是对回复的响应，并表示该范围内最高和最矮奶牛之间的高度差。

样例输入

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

样例输出

6 
3 
0

样例说明

无

数据范围

$100\%$数据满足：$1 \le N \le 50,000$ ,$1 \le Q \le 200,000,1 \le height \le 1,000,000$ 。