seuOJ333 - 求和

题目描述

某人热爱数据结构。为了展示他的热爱，并不失风度，他在黑板上写下这样一个式子：

∑l=LR∑r=lRmin⁡i=lrai\sum_{l=L}^R \sum_{r=l}^R \min_{i=l}^r a_i

他徐徐解释道：今天的问题是，给定一个长度为 nn 的序列 a1,a2,...,ana_1,a_2,...,a_n，有 qq 次询问，每次询问指定一个区间 [L,R][L,R]，求

∑l=LR∑r=lRmin⁡i=lrai\sum_{l=L}^R \sum_{r=l}^R \min_{i=l}^r a_i

输入格式

第一行包含两个正整数 n,q(1≤n,q≤2021)n,q(1 \le n,q \le 2021)，表示序列的长度和询问的组数。

第二行包含 nn 个整数，第 ii 个整数表示 ai(∣ai∣≤109)a_i (|a_i| \le 10^9)。

接下来 qq 行，每行包含两个整数 L,RL,R，表示一次询问。

输出格式

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

样例

样例输入

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

样例输出

4
7
10
22
35