2231. 序列

给定长度为 $n$ 的序列:$a_1,a_2,…,a_n$,记为 $a[1:n]$。

类似地,$a[l:r]$($1≤l≤r≤N$) 是指序列:$a_l,a_{l+1},…,a_{r-1},a_r$。

若 $1≤l≤s≤t≤r≤n$,则称 $a[s:t]$ 是 $a[l:r]$ 的子序列。

现在有 $q$ 个询问,每个询问给定两个数 $l$ 和 $r$,$1≤l≤r≤n$,求 $a[l:r]$ 的不同子序列的最小值之和。

例如,给定序列 $5,2,4,1,3$,询问给定的两个数为 $1$ 和 $3$,那么 $a[1:3]$ 有 $6$ 个子序列 $a[1:1],a[2:2],a[3:3],a[1:2],a[2:3],a[1:3]$,这 $6$ 个子序列的最小值之和为 $5+2+4+2+2+2=17$。

输入格式

第一行包含两个整数 $n$ 和 $q$,分别代表序列长度和询问数。

接下来一行,包含 $n$ 个整数,以空格隔开,第 $i$ 个整数为 $a_i$,即序列第 $i$ 个元素的值。

接下来 $q$ 行,每行包含两个整数 $l$ 和 $r$,代表一次询问。

输出格式

对于每次询问,输出一行,代表询问的答案。

数据范围

$1 \le n,q \le 10^5$,
$|a_i| \le 10^9$

输入样例:

5 5
5 2 4 1 3
1 5
1 3
2 4
3 5
2 5

输出样例:

28
17
11
11
17