题目描述

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

你有一个序列$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$。