Sum of Subarray Minimums for Queries

Given a sequence of length \( n \): \( a_1, a_2, \cdots, a_n \) (denoted as \( a[1:n] \)), a contiguous subarray \( a[l:r] \) for \( 1 \leq l \leq r \leq n \) is defined as \( a_l, a_{l+1}, \cdots, a_r \). Note that if \( 1 \leq l \leq s \leq t \leq r \leq n \), then \( a[s:t] \) is called a subarray of \( a[l:r] \).

You are given \( q \) queries. Each query contains two integers \( l \) and \( r \) (with \( 1 \leq l \leq r \leq n \)). For each query, compute the sum of the minimum values of all contiguous subarrays of \( a[l:r] \).

For example, given the sequence \( 5,\ 2,\ 4,\ 1,\ 3 \) and a query with \( l=1 \) and \( r=3 \), the contiguous subarrays of \( a[1:3] \) are: \( a[1:1]=[5] \), \( a[2:2]=[2] \), \( a[3:3]=[4] \), \( a[1:2]=[5,2] \), \( a[2:3]=[2,4] \), \( a[1:3]=[5,2,4] \). The minimum values of these subarrays are \( 5,\ 2,\ 4,\ 2,\ 2,\ 2 \) respectively, and their sum is \( 17 \).

Note: The answer for each query is calculated by summing the minimum element of every contiguous subarray in \( a[l:r] \). Efficient solutions may preprocess the array to answer queries quickly.

inputFormat

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

The second line contains \( n \) space-separated integers \( a_1, a_2, \ldots, a_n \).

Then \( q \) lines follow, each containing two integers \( l \) and \( r \) (\( 1 \le l \le r \le n \)) representing a query.

outputFormat

For each query, output a single integer on a new line: the sum of the minimum values of all contiguous subarrays of \( a[l:r] \).

sample

5 1
5 2 4 1 3
1 3

17