【UNR #10】麦田
在金黄色的麦田里，Mugi 正在守护一排共 $n$ 株的麦穗。排列成一线的麦穗，从左到右依次编号为 $1$ 到 $n$，其中第 $i$ 株麦穗的初始高度为 $b_i$。
每一天，当清风拂过麦田时，所有严格矮于左右相邻麦穗的麦穗，高度都会同时变为左右两侧高度的较大值。形式化地，对于高度序列 $a$，所有满足 $a_i < a_{i-1}$ 且 $a_i < a_{i+1}$（其中 $1 < i < |a|$）的位置都会同时变为 $\max(a_{i-1}, a_{i+1})$。
Mugi 进行了 $q$ 次独立询问，每次给定区间 $[l, r]$。他将该区间内的麦穗视作一个独立序列，请你求出该区间的麦穗经过 $10^{99}$ 天后达到的高度和。
输入格式
第一行包含两个正整数 $n$ 和 $q$。
第二行包含 $n$ 个正整数，表示初始高度序列 $b_i$。
接下来 $q$ 行，每行包含两个正整数 $l$ 和 $r$，表示询问的区间。
输出格式
对于每次询问，输出一行一个整数，分别表示区间内麦穗经过 $10^{99}$ 天后达到的最大高度和。
5 3
5 1 2 1 5
1 3
2 4
1 5
12
4
25
对于询问 $[1,3]$，序列为 $[5,1,2]$。第 $1$ 天，$1$ 严格小于左右两侧的 $5,2$，变为 $\max(5,2)=5$，序列变为 $[5,5,2]$，答案为 $5+5+2=12$。
对于询问 $[2,4]$，序列为 $[1,2,1]$。中间的 $2$ 不会变化，答案为 $1+2+1=4$。
对于询问 $[1,5]$，序列为 $[5,1,2,1,5]$。第 $1$ 天变为 $[5,5,2,5,5]$，第 $2$ 天变为 $[5,5,5,5,5]$，答案为 $5+5+5+5+5=25$。
样例二-五
见附件下载。
数据范围
对于所有数据，满足 $1\le n,q\le 1\times 10^6$，$1\le b_i\le 10^9$。
| 子任务编号 | 约束 | 分值 |
|---|---|---|
| $1$ | $n,q\le 8, b_i\le 10$ | $10$ |
| $2$ | $n\le 5000,q\le 5$ | $20$ |
| $3$ | 所有询问区间长度之和 $\le 2\times 10^6$ | $20$ |
| $4$ | $n,q\le 5\times 10^4$ | $20$ |
| $5$ | $n,q\le 2\times 10^5$ | $20$ |
| $6$ | $n,q\le 1\times 10^6$ | $10$ |
本题读入量较大，建议使用较快的输入输出方式。我们在附件中提供了一个输入输出模板 template.cpp。
时间限制：$\texttt{1s}$
空间限制：$\texttt{1GB}$