Alexey is playing with an array, , of integers. His friend, Ivan, asks him to calculate the sum of the maximum values for all subsegments of . More formally, he wants Alexey to find .
Alexey solved Ivan's challenge faster than expected, so Ivan decides to add another layer of difficulty by having Alexey answer queries. The query contains subsegment , and he must calculate the sum of maximum values on all subsegments inside subsegment .
More formally, for each query , Alexey must calculate the following function:
.
Can you help Alexey solve this problem?
Input Format
The first line contains space-separated positive integers, (the length of array ) and (number of queries), respectively.
The second line contains space-separated integers, describing each element (where ) in array .
Each of the subsequent lines contains space-separated positive integers describing the respective values for and in query (where ).
Constraints
Output Format
For each query (where ), print its answer on a new line.
Sample Input
3 6
1 3 2
1 1
1 2
1 3
2 2
2 3
3 3
Sample Output
1
7
15
3
8
2
Explanation
The answer for the second query is shown below:
The answer for the third query is shown below: