题目描述

给定一个长度为 $n$​ 的正整数序列 $a$。

江桥可以选择一个位置 $i$，对应初始区间为 $[i,i]$。

每次江桥可以选择将区间向左扩一个位置，或者向右扩一个位置。但要求新增加的这个位置上的元素的值要大于扩展前的区间的元素和。

例如，如果 $i > 1$ 且 $a_{i - 1} > a_i$，那么区间 $[i,i]$ 可以扩展为 $[i - 1,i]$。

如果 $i < n$ 且 $a_{i + 1} > a_i$，那么区间 $[i,i]$ 可以扩展为 $[i,i + 1]$。

如果 $i+1 < n$ 且 $a_{i+2} > a_i + a_{i + 1}$，那么区间 $[i,i + 1]$ 可以扩展为 $[i,i + 2]$。

因此 $[i,i]$ 作为初始区间，可以扩展成若干个区间。

称 $[i,i]$ 作为初始区间，能扩展出的区间和最大的区间为 $i$ 的最大扩展区间。

江桥需要你回答 $q$ 次查询，每次查询给你两个正整数 $l,r$。

你需要回答该序列分别以 $[l,l],[l + 1,l+1]...,[r,r]$ 作为初始区间，对应的 $r - l + 1$ 个最大扩展区间的值的和。

江桥又双叒叕被难住了，现在他请你来帮他解决这个问题。

输入格式

第一行有两个正整数 $n,q$，表示序列长度和询问次数。

接下来一行 $n$ 个正整数 $a_i$，含义如上所述。

接下来 $q$ 行，每行两个正整数 $l_i,r_i$，表示操作。

输出格式

对于每次查询，输出一行一个整数表示答案。

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

5
15
30

样例解释

对于第一次查询，$2$ 位置最大扩展区间为 $[2,3]$，因此答案为 $1 + 4 = 5$。

对于第二次查询，前三个位置的最大扩展区间分别为 $[1,1],[2,3],[3,4]$，因此答案为 $1 + 1 + 4 + 4 + 5= 15$。

数据规模与约定

下发文件

下发文件分别对应子任务 $1$、$4$。

有合理的子任务依赖。

子任务编号	$n≤$	$q≤$	分值
$1$	$30$	$3 \times 10^5$	$10$
$2$	$10^2$		$20$
$3$	$10^{4}$	$1$	$30$
$4$		$3 \times 10^5$	$40$

对于100%的数据：$1 \leq n \leq 10^4, 1 \leq q \leq 3 \times 10^5,1 \leq a_i \leq 10^9,1 \leq l_i \leq r_i \leq n$。

每个子任务必须全部通过才得分。