[HNOI2016] 序列

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

给定长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$。

对每次询问给出的 $l,r$，考虑所有满足 $l\le s\le t\le r$ 的连续子段 $a_s,a_{s+1},\ldots,a_t$。请计算这些连续子段的最小值之和。

输入格式

第一行输入两个整数 $n,q$，分别表示序列长度和询问数。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $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

数据范围

对于所有数据，保证 $1\le n,q\le 10^5$，$|a_i|\le 10^9$，$1\le l\le r\le n$。