#2051. 「HNOI2016」序列

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给定长度为 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