#2051. 「HNOI2016」序列

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

题目描述

给定长度为 n n 的序列:a1,a2,,an a_1, a_2, \cdots , a_n ,记为 a[1 ⁣:n] a[1 \colon n] 。类似地,a[l ⁣:r] a[l \colon r] 1lrN 1 \leq l \leq r \leq N)是指序列:al,al+1,,ar1,ar a_{l}, a_{l+1}, \cdots ,a_{r-1}, a_r 。若 1lstrn1\leq l \leq s \leq t \leq r \leq n,则称 a[s ⁣:t] a[s \colon t] a[l ⁣:r] a[l \colon r] 的子序列。

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

输入格式

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

输出格式

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

样例

样例输入

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

样例输出

28 
17 
11 
11 
17

数据范围与提示

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