FIICode 2025 Qualifying Round - Elevi | Accent

$\textit{The accent is on 'pe'.} \\ \rule{6cm}{0.4pt} \\ \textit{--Dan The Badger, Uncountable Talents}$

Task

Dan The Badger and Sorin The Golden Child gathered in the studio one day to solve a problem. Dan told Sorin that for any array the accent falls on the third smallest number. Thus, we can denote $f(b_1,b_2,...,b_k)$ to be the third smallest number (including duplicates) among $b_1$, $b_2$,..., $b_k$. For example, $f(1,2,3)=3$ and $f(2,1,1,3)=2$.

Now, they have an array $[a_1,a_2,\ldots, a_n]$ and $q$ queries of the form $(l,r)$ for which they have to determine the following:

$\displaystyle \sum_{i = l}^{r-2} \sum_{j = i+2}^r f(a_i,a_{i+1},...,a_{j})$

Input data

The first line of input contains the numbers $n$ and $q$ ($3 \le n,q \le 5 \cdot 10^5$).

The second line contains $n$ numbers $a_1$, $a_2$,..., $a_n$ ($1 \le a_i \le 10^6$).

The next $q$ lines contain two numbers, $l$ and $r$ ($1 \le l,r \le n$ and $r \ge l+2$), denoting a query.

Output data

The first $q$ lines will contain one number each, representing the answer for the corresponding query.

Example

stdin

6 4
1 2 4 3 4 4
2 4
1 4
3 6
1 6

stdout

4
11
12
37

Explanation

For the first query, we have $f(2,4,3) = 4$.

For the second query, we have $f(1,2,4) + f(2,4,3) + f(1,2,4,3) = 4 + 4 + 3 = 11$.

For the third query, we have $f(4,3,4) + f(3,4,4) + f(4,3,4,4) = 4 + 4 + 4 = 12$