题目描述

农夫约翰的 $n$ 头奶牛 $(1 \le n \le 50000)$ 每天都按照相同的顺序排队挤奶。有一天，约翰决定和其中一些奶牛玩终极飞盘比赛。为了简单起见，他将从挤奶队列中取出一段连续的奶牛来参加比赛。然而，为了让所有的奶牛都能玩得开心，它们的身高差异不应该太大。

约翰列出了 $q (1 \le q \le 200000)$ 组潜在的奶牛及其身高 $(1 \le h \le 10^6)$ 的清单。对于每组奶牛，他希望你帮助确定该组中最高和最矮奶牛之间的身高差。

输入格式

第 $1$ 行: 两个用空格分隔的整数，$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\sim q$ 行: 每行包含一个整数，表示对应询问的最高和最矮奶牛身高之间的差值。

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

6
3
0