给定长度为 n 的序列：a1 ,a2 ,…,an ，记为 a[1:n]。类似地，a[l:r]（1 ≤ l ≤ s ≤ n）是指序列：al,al+1 ,…,ar−1 ,ar。若1 ≤ l ≤ s ≤ t ≤ r ≤ n，则称 a[s:t]是 a[l:r]的子序列。
现在有 q个询问，每个询问给定两个数 l 和 r，1 ≤ l≤ s ≤ 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个整数位ai，即序列第i个元素的值。
接下来的q行，每行包含两个整数l和r，代表 一次询问。

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

【样例解释】
在第一个询问中，a[1:5]所有的子序列和对应的最小值为：

其和为28.
【数据规模和约定】
所有测试点的数据规模如下：

栈 前缀和 AHOI高中 2016 level7