D - Division into 3 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MiB

配点 : 700 点

問題文

長さ 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 以上になるため，3 つの非空な連続部分列に分割する方法は必ず 1 つ以上存在する．

制約

  • 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
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

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

出力例 1

10
5
6
9
8

1 つめのクエリについて説明します． B=(4,3,1,1,4,5,2) です． これを (4,3),(1,1),(4,5,2) と分解すると，各連続部分列の最大値は 4,1,5 となり，その総和は 10 になります． この総和が 10 より小さくなる方法は存在しないので，このクエリの答えは 10 になります．

入力例 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

出力例 2

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

Score : 700 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\cdots,A_N) of length N. Answer the following Q queries.

  • The i-th query: You are given integers L_i and R_i. Solve the following problem for B=(A_{L_i},A_{L_i+1},\cdots,A_{R_i}).
    • Divide B into three non-empty contiguous subsequences. For each contiguous subsequence, let us find the maximum value of its elements. Find the minimum possible sum of these maximum values. Here, the constraints of the problem force the length of B to be at least 3, so there is always at least one way to divide it into three non-empty contiguous subsequences.

Constraints

  • 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
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 1

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

Sample Output 1

10
5
6
9
8

Let us explain the first query. We have B=(4,3,1,1,4,5,2). If you divide it into (4,3),(1,1),(4,5,2), the maximum values of the contiguous subsequences are 4,1,5, respectively, and their sum is 10. There is no way to make this sum smaller, so the answer to this query is 10.

Sample Input 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

Sample Output 2

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