题目描述

小 A 有一个 $n$ 个点的完全图（点之间两两有连边），初始时第 $i$ 个点有点权 $a_i$。任意两点之间的边权定义为两端点权之和。

你需要回答小 A 的 $q$ 个问题，每次小 A 会给定一个区间 $l,r$，表示只考虑编号在 $[l,r]$ 内的点，以及这些点之间的边，求其最小生成树的边权和。

输入格式

第一行两个正整数 $n,q$。

第二行 $n$ 个正整数 $a_i$，表示点权。

接下来 $q$ 行，每行两个数字 $l,r$ 表示一次询问。

输出格式

对于每个询问，输出一行一个正整数，表示答案。

样例

样例输入 #1

1 1
1
1 1

样例输出 #1

0

样例输入 #2

3 3
1 3 2
1 2
2 3
1 3

样例输出 #2

4
5
7

数据范围与约定

对于所有数据，$1\le n,q\le 200000,1\le a_i\le 10^9$。