题目背景

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

题目描述

有 $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,\dots, 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\leq 10^9$
• $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\leq 10^5,Q\leq 10^5,H_i\leq2(0\leq i\leq N-1)$；
4. ($24$ 分) $N\leq 10^5,Q\leq 10^5,H_i\leq20(0\leq i\leq N-1)$；
5. ($40$分) 没有附加限制。

Author

Riku Kawasaki (Japan)

Source

IOI 2018 D2T3