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

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

来自每座山 y（L_j≤y≤R_j）的参会者的成本，等于在山 x 和 y 之间（包含 x 和 y）的所有山的最大高度。特别地，来自山 x 的参会者的成本是 H_x，也就是山 x 的高度。 会议的成本等于其所有参会者的成本之和。 你想要用最低的成本来举办每个会议。

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

输入格式 第一行：N Q 第二行：H_0 H_1 … H_{N-1} 第 3+j 行（0≤j≤Q-1）：L_j R_j

输出格式 第 1+j 行（0≤j≤Q-1）：C_j（C_j 为举办会议 j 的最低可能成本）

样例 输入

4 2
2 4 3 5
0 2
1 3

输出

10
12

数据范围与提示 对于全部数据： 1≤N,Q≤7.5×10^5 1≤H_i≤10^9（0≤i≤N-1） 0≤L_j≤R_j≤N-1 且保证区间两两不同（0≤j≤Q-1）。

子任务 （4 分）N≤3000，Q≤10 （15 分）N≤5000，Q≤5000 （17 分）N,Q≤10^5，H_i≤2（0≤i≤N-1） （24 分）N,Q≤10^5，H_i≤20（0≤i≤N-1） （40 分）没有附加限制