该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小明出题出烦了，于是决定搬一道题来：

你有一个序列 $A$，长度是 $N$，每个位置 $A_i$ 都是正整数。

然后有 $Q$ 次询问。

每次给出 $L,R$，问：把 $[A_L,A_R]$ 划分成恰好三个非空区间，三个区间的最大值的和，最小是多少？

输入格式

第一行输入 $N,Q$。

第二行输入 $N$ 个数字 $A_1,...,A_N$。

接下来 $Q$ 行，每行两个整数 $L_i,R_i$。

输出格式

对于每组询问，输出一个答案。

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

10
5
6
9
8

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

数据范围

对于 $5\%$ 的数据：$N,Q\leq 50$。

对于 $20\%$ 的数据：$N,Q\leq 100$。

对于 $40\%$ 的数据：$N,Q\leq 5000$。

对于 $70\%$ 的数据：$N,Q\leq 10^5$。

对于 $100\%$ 的数据：$N,Q\leq 2.5\times 10^5,1\leq A_i\leq 10^8,R_i-L_i\geq 2$。