← 返回题目列表

AtCoder · arc180_d

D. 分为3

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

给你一个整数序列 A=(A_1,A_2,\cdots,A_N) 长度 N。 回答以下问题 Q 查询。

  • 的 i-th 查询:您得到整数 L_i 和 R_i。 解决以下问题 B=(A_{L_i},A_{L_i+1},\cdots,A_{R_i}).
    • 除法 B 分成三个非空连续子序列。对于每个连续的子序列,让我们找到其元素的最大值。找出这些最大值的最小可能总和。 在这里,问题的约束迫使 B 至少 3,因此总是至少有一种方法将其分为三个非空连续子序列。

约束

  • 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

让我们解释一下第一个查询。 我们有 B=(4,3,1,1,4,5,2)。 如果你把它分成 (4,3),(1,1),(4,5,2),连续子序列的最大值为 4,1,5分别,它们的总和是 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