AT_arc180_d [ARC180D] Division into 3

给定一个长度为 $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$ 个查询的答案。

## 限制条件 - $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 翻译