静态区间极差

难度：T4

【知识点：ST表】

前置知识：ST表及其冻结前置单元。

题目描述与输入

输入$n$、$q$，随后$n$个整数，再输入$q$行$1$起点闭区间$l$、$r$。

输出

每问输出区间最大值减最小值。

数据范围

$1$<=$n,q<=2000$；$1$<=$l<=r<=n$；|a_$i$|<=$10^9$。

样例输入

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

样例输出

6
4
0

样例说明

分别维护幂等的$min$与$max$表，不直接维护可重叠相加的和。请按输入操作顺序逐步核对；没有规定输出的更新操作不输出额外内容。