题目描述

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\cdots,A_N)$。请回答以下 $Q$ 个查询。

• 第 $i$ 个查询：给定整数 $L_i,R_i$。对于 $B=(A_{L_i},A_{L_i+1},\cdots,A_{R_i})$，解决如下问题：
  • 将 $B$ 分割为 $3$ 个非空的连续子序列。对于每个连续子序列，求出其元素的最大值。求这些最大值之和可能取得的最小值。注意，由于题目限制，$B$ 的长度至少为 $3$，因此一定存在至少一种分割方法。

输入格式

输入以如下格式从标准输入给出。

$N$ $Q$ $A_1$ $A_2$ $\cdots$ $A_N$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_Q$ $R_Q$

输出格式

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个查询的答案。

样例 1

输入

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

输出

10
5
6
9
8

样例 2

输入

10 15
8 3 8 10 1 5 3 1 6 4
4 6
2 5
6 9
8 10
2 9
4 10
1 5
1 8
1 3
4 8
1 10
2 10
6 10
2 6
2 6

输出

16
14
12
11
17
17
19
14
19
14
17
17
12
16
16

说明/提示

限制条件

• $3\leq N\leq 250000$
• $1\leq Q\leq 250000$
• $1\leq A_i\leq 10^8$
• $1\leq L_i\leq R_i\leq N$
• $R_i-L_i\geq 2$
• 输入的所有值均为整数

样例解释 1

以第 $1$ 个查询为例。$B=(4,3,1,1,4,5,2)$。将其分割为 $(4,3),(1,1),(4,5,2)$ 时，各连续子序列的最大值分别为 $4,1,5$，其总和为 $10$。不存在比 $10$ 更小的分割方式，因此该查询的答案为 $10$。

由 ChatGPT 4.1 翻译