Sum of Subarray Minimums in a Given Range

You are given a sequence \(a_1, a_2, \cdots, a_n\) (denoted as \(a[1:n]\)). For a subarray \(a[l:r]\) (with \(1 \le l \le r \le n\)), all its contiguous subarrays are defined as \(a[s:t]\) where \(l \le s \le t \le r\).

For each query consisting of two integers \(l\) and \(r\), you need to calculate the sum of the minimum elements of every contiguous subarray of \(a[l:r]\). That is, if \(f(l, r)\) denotes the required sum then

[ f(l,r)=\sum_{l \leq s \leq t \leq r} \min{a_s,a_{s+1},\dots,a_t}, ]

For example, if the sequence is 5, 2, 4, 1, 3 and the query is \(l=1, r=3\), then the subarray \(a[1:3] = [5,2,4]\) has 6 contiguous subarrays:

• \(a[1:1]\): [5] → minimum is 5
• \(a[2:2]\): [2] → minimum is 2
• \(a[3:3]\): [4] → minimum is 4
• \(a[1:2]\): [5,2] → minimum is 2
• \(a[2:3]\): [2,4] → minimum is 2
• \(a[1:3]\): [5,2,4] → minimum is 2

The answer for this query is \(5+2+4+2+2+2=17\).

Note: The input size is not huge, so an \(O(n^2)\) solution per query is acceptable.

inputFormat

The first line contains two integers \(n\) and \(q\) --- the length of the sequence and the number of queries.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the sequence.

Each of the next \(q\) lines contains two integers \(l\) and \(r\) (\(1 \le l \le r \le n\)), representing a query.

outputFormat

For each query, output a single line containing the sum of the minimums of every contiguous subarray of \(a[l:r]\).

sample

5 1
5 2 4 1 3
1 3

17