题目描述
给定长度为 $n$ 的序列：$a_1, a_2, \dots, a_n$，记为 $a[1:n]$。类似地，$a[l:r]$（$1 \le l \le r \le n$）是指序列：$a_l, a_{l+1}, \dots, a_{r-1}, a_r$。若 $1 \le l \le s \le t \le r \le n$，则称 $a[s:t]$ 是 $a[l:r]$ 的子序列。
现在有 $q$ 个询问，每个询问给定两个数 $l$ 和 $r$（$1 \le l \le r \le 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$，代表一次询问。
输出格式
对于每次询问，输出一行，代表询问的答案。
数据范围
所有测试点的数据规模如下：
| 测试点编号 | $n$ | $q$ | 备注 |
|---|---|---|---|
| 1 | $n \le 100$ | $q \le 100$ | 序列中任意两元素值不同 |
| 2 | $n \le 100000$ | $q \le 100000$ | 无 |
| 3 | $n \le 5000$ | $q \le 10$ | 无 |
| 4 | $n \le 5000$ | $q \le 10$ | 无 |
| 5 | $n \le 100000$ | $q \le 10$ | 无 |
| 6 | $n \le 100000$ | $q \le 100000$ | 无 |
| 7 | $n \le 100000$ | $q \le 100000$ | 无 |
| 8 | $n \le 100000$ | $q \le 100000$ | 无 |
| 9 | $n \le 100000$ | $q \le 100000$ | 无 |
| 10 | $n \le 100000$ | $q \le 100000$ | 无 |
对于所有测试数据，$1 \le n, q \le 100000$，$|a_i| \le 10^9$。
样例
样例输入 1
5 5 5 2 4 1 3 1 5 1 3 2 4 3 5 2 5
样例输出 1
28 17 11 11 17
说明
在第一个询问中，$a[1:5]$ 所有的子序列和对应的最小值为：
$a[1:1]: 5$ $a[1:2]: 2$ $a[1:3]: 2$ $a[1:4]: 1$ $a[1:5]: 1$ $a[2:2]: 2$ $a[2:3]: 2$ $a[2:4]: 1$ $a[2:5]: 1$ $a[3:3]: 4$ $a[3:4]: 1$ $a[3:5]: 1$ $a[4:4]: 1$ $a[4:5]: 1$ $a[5:5]: 3$
其和为 $28$。