[HNOI2016] 序列

题目描述

给定长度为 $ 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 $,代表一次询问。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

28 
17 
11 
11 
17

说明

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