题目描述

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

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

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

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

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

实现细节

你需要实现下面的函数：

int64[] minimum_costs(int[] H, int[] L, int[] R)

• H：长度为 $N$ 的数组，表示这些山的高度。
• L 和 R：两个长度为 $Q$ 的数组，表示这些会议的参会者的范围。
• 该函数应返回一个长度为 $Q$ 的数组 $C$。$C_j$（$0\le j\le Q-1$）必须是举办会议 $j$ 的最低的可能成本。

• 注意，$N$ 和 $Q$ 的值是数组的长度，题目中所有数组均用 vector 实现。

  由于本题的特殊性，改为传统题方式测评。

输入格式

评测程序示例读取如下格式的输入数据（即为输入格式）：

• 第一行：$N\ Q$
• 第二行：$H_0\ H1\ \ldots \ H{N-1}$
• 第 $3+j$ 行（$0\le j\le Q-1$）：$L_j\ R_j$

评测程序示例将以如下格式输出 minimum_costs 的返回值（即为输出格式）：

• 第 $1+j$ 行（$0\le j\le Q-1$）：$C_j$

样例

input

4 2
2 4 3 5
0 2
1 3

output

10
12

数据范围与提示

对于全部数据：

• $1\le N,Q\le 7.5\times 10^5$
• $1\le H_i\le 10^9$ $(0\le i\le N-1)$
• $0\le L_j\le R_j\le N-1$ 且保证区间两两不同（$0\le j\le Q-1$）。

子任务

1. （4 分）$N\le 3000,Q\le 10$
2. （15 分）$N\le 5000,Q\le 5000$
3. （17 分）$N,Q\le 10^5,H_i\le 2\ (0\le i\le N-1)$
4. （24 分）$N,Q\le 10^5,H_i\le 20\ (0\le i\le N-1)$
5. （40 分）没有附加限制