该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile2051.zip](file://AdditionalFile2051.zip?type=additional_file)

#2051. 「HNOI2016」序列

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

给定长度为 $n$ 的序列：$a_1, a_2, \cdots , a_n$，记为 $a[1 \colon n]$。类似地，$a[l \colon r]$（$1 \leq l \leq r \leq N$）是指序列：$a_{l}, a_{l+1}, \cdots ,a_{r-1}, a_r$。若 $1\leq l \leq s \leq t \leq r \leq n$，则称 $a[s \colon t]$是 $a[l \colon r]$ 的子序列。

现在有 $q$ 个询问，每个询问给定两个数 $l$ 和 $r$，$1 \leq l \leq r \leq n$，求 $a[l \colon r]$ 的不同子序列的最小值之和。例如，给定序列 $5, 2, 4, 1, 3$，询问给定的两个数为 $1$ 和 $3$，那么 $a[1 \colon 3]$ 有 $6$ 个子序列 $a[1 \colon 1], a[2 \colon 2], a[3 \colon 3], a[1 \colon 2],a[2 \colon 3], a[1 \colon 3]$，这 $6$ 个子序列的最小值之和为 $5+2+4+2+2+2=17$。

输入格式

输入文件的第一行包含两个整数 $n$ 和 $q$，分别代表序列长度和询问数。
接下来一行，包含 $n$ 个整数，以空格隔开，第 $i$ 个整数为 $a_i$，即序列第 $i$ 个元素的值。
接下来 $q$ 行，每行包含两个整数 $l$ 和 $r$，代表一次询问。

输出格式

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

样例

输入

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

输出

28
17
11
11
17

数据范围与提示

对于 $100\%$ 的数据，$1 \leq n,q \leq 100000 ,|a_i| \leq 10^9$