QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
Statistics

老 M 是一个知名的混元形意太极大师,经常会有仰慕者前来拜师学艺,但他们必须经过严格的入学考试:爬楼梯。

老 M 的道场有 $n$ 个平台排成一列,第 $i$ 个平台的高度为 $h_i$,从第 $i$ 个平台爬楼梯到第 $i+1$ 个平台所需要消耗的体力为 $|h_i-h_{i+1}|$。

当第 $j$ 个仰慕者来拜师学艺时,老 M 会指定一个区间 $[l_j, r_j]$,取出这个区间内的所有平台,并使用内功将他们重新排列(不改变原序列),使得爬完所有楼梯消耗的体力值之和最大,即 $\max_{p \in S} \sum_{i=l_j}^{r_j-1} |p_i-p_{i+1}|$,其中 $S$ 表示将 $\{h_{l_j}, h_{l_j+1}, \dots, h_{r_j}\}$ 重新排列能得到的序列的集合。但老 M 在忙着打 MMA,因此他想请你——M 氏混元形意太极拳的第 $992\,844\,853$ 个真传弟子,计算这个最大值。

输入格式

第一行两个正整数 $n, m$,分别表示平台的个数与仰慕者总数。

第二行 $n$ 个正整数 $h_1\sim h_n$,依次表示平台 $1\sim n$ 的高度。

接下来 $m$ 行,第 $i$ 行两个正整数 $l_i, r_i$($1 \le l_i < r_i \le n$),表示有新的仰慕者来拜师学艺,你需要回答区间 $[1_i,r_i]$ 经过重排列后,耗费的最大体力值。

输出格式

$m$ 行,第 $i$ 行一个整数,表示第 $i$ 位仰慕者花费的最大体力值。

样例数据

样例输入

4 4
3 2 2 4
1 3
1 4
2 4
2 3

样例输出

2
5
4
0

样例解释

第一次询问,一种最优的方案为 $[2,3,2]$,耗费体力值为 $2$。

第二次询问,一种最优的方案为 $[3,2,4,2]$,耗费体力值为 $5$。

第三次询问,一种最优的方案为 $[2,4,2]$,耗费体力值为 $4$。

第四次询问,一种最优的方案为 $[2,2]$,耗费体力值为 $0$。

数据范围

子任务 1($5\%$):$n, m \le 10$;

子任务 2($10\%$):$h_i \le 2$;

子任务 3($20\%$):$h_i \le 3$;

子任务 4($25\%$):$n, m \le 2000$;

子任务 5($40\%$):无附加限制。

对于所有数据,有 $2 \le n, m \le 200\,000$,$1 \le h_i \le 10^9$。

保证对于所有询问,满足 $1 \le l_i < r_i \le n$。