P5044 [IOI 2018] meetings 会议

本题为交互题，但在此请提交**完整程序**。 本题因为测试点过多，文件过大，只选择了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$ 的高度。 - 会议的成本等于其所有参会者的成本之和。 你想要用最低的成本来举办每个会议。 注意，所有的参会者将在每次会议后回到他们自己的山；所以一个会议的成本不会受到先前会议的影响。

无

无

### 样例#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