题目背景

本题为交互题，但在此请提交完整程序。

本题因为测试点过多，文件过大，只选择了33个测试点进行测评（涵盖了所有子任务）。剩余11组数据可下载数据自行测评。

https://ioi2018.jp/wp-content/tasks/contest2/meetings.zip

题目描述

有 $N$ 座山横着排成一行，从左到右编号为从 $0$ 到 $N-1$。山的高度为 $H_i$（$0\leq i\leq N-1$）。每座山的顶上恰好住着一个人。

你打算举行 $Q$ 个会议，编号为从 $0$ 到 $Q-1$。会议 $j$（$0\leq j\leq Q-1$） 的参加者为住在从山 $L_j$ 到山 $R_j$（包括 $L_j$ 和 $R_j$）上的人（$0\leq L_j\leq R_j\leq N-1$）。对于该会议，你必须选择某个山 $x$ 做为会议举办地（$L_j\leq x\leq R_j$）。举办该会议的成本与你的选择有关，其计算方式如下：

• 来自每座山 $y$（$L_j\leq y\leq R_j$） 的参会者的成本，等于在山 $x$ 和 $y$ 之间（包含 $x$ 和 $y$）的所有山的最大高度。特别地，来自山 $x$ 的参会者的成本是 $H_x$，也就是山 $x$ 的高度。

• 会议的成本等于其所有参会者的成本之和。

你想要用最低的成本来举办每个会议。

注意，所有的参会者将在每次会议后回到他们自己的山；所以一个会议的成本不会受到先前会议的影响。

输入格式

输入的第一行包含两个正整数 $N$ 和 $Q$，其意义见题目描述。

第二行包含 $N$ 个正整数 $H_0,H_1,\cdots, H_{N-1}$，表示这些山的高度。

第 $3+j$ 行（$0\leq j\leq Q-1$），每行两个整数 $L_j, R_j$，表示这些会议的参会者的范围。

输出格式

共 $Q$ 行，第 $1+j$ 行（$0\leq j\leq Q-1$）一个整数 $C_j$，表示举办会议 $j$ 的最低的可能成本。

4 2
2 4 3 5
0 2
1 3

10
12

3 3
2 1 2
0 0
0 1
0 2

2
3
5

5 1
1000000000 1000000000 1 1000000000 1000000000
0 4

4000000001

15 10
10 71 84 33 6 47 23 25 52 64 70 31 22 31 2
5 10
3 7
0 13
8 12
0 0
1 3
7 13
1 13
10 12
1 1

281
180
828
263
10
201
364
744
123
71

提示

样例#1解释

会议$j=0$有$L_j=0$和$R_j=2$，所以将由住在山$0$、$1$和$2$上的人参加。如果山$0$被选做举办地，会议$0$的成本计算如下：

• 住在山$0$上的参会者的成本是$\max\lbrace H_0\rbrace=2$。
• 住在山$1$上的参会者的成本是$\max\lbrace H_0,H_1\rbrace=4$。
• 住在山$2$上的参会者的成本是$\max\lbrace H_0,H_1,H_2\rbrace=4$。
• 因此，会议$0$的成本是$2+4+4=10$。

不可能以更低的成本来举办会议$0$了，因此会议$0$的最低成本是$10$。

会议$j=1$有$L_j=1$和$R_j=3$，因此将由住在山$1$、$2$和$3$上的人参加。如果山$2$被选做举办地，会议$1$的成本计算如下：

• 住在山$1$上的参会者的成本是$\max\lbrace H_1,H_2\rbrace=4$。
• 住在山$2$上的参会者的成本是$\max\lbrace H_2\rbrace=3$。
• 住在山$3$上的参会者的成本是$\max\lbrace H_1,H_2,H_3\rbrace=5$。
• 因此，会议$1$的成本是$4+3+5=12$。

不可能以更低的成本来举办会议$1$了，所以会议$1$的最低成本是$12$。

限制条件

• $1\leq N\leq 750\space000$
• $1\leq Q\leq 750\space000$
• $1\leq H_i\leq1\space000\space000\space000$
• $0\leq L_j\leq R_j\leq R-1(0\leq j\leq Q-1)$
• $(L_j,R_j)\neq(L_k,R_k)(0\leq j<k\leq Q-1)$

子任务

1. (4分) $N\leq3000,Q\leq10$
2. (15分) $N\leq5000,Q\leq5000$
3. (17分) $N\leq100\space000,Q\leq100\space000,H_i\leq2(0\leq i\leq N-1)$
4. (24分) $N\leq100\space000,Q\leq100\space000,H_i\leq20(0\leq i\leq N-1)$
5. (40分) 没有附加限制

Author

Riku Kawasaki (Japan)

Source

IOI 2018 D2T3