Alice and Bob reside in separate worlds. No matter how deeply they yearn to communicate, the universe answers only with an indifferent silence. Between their worlds lies a vast, quiet border where $n$ ancient gates stand in a row. These gates have lain dormant for millennia until one day, perhaps moved by Alice and Bob's wishes, they begin to awaken.

The $i$-th gate awakens on day $p_i$. No two gates awaken on the same day; thus, the sequence $p_1,p_2,\ldots,p_n$ is a permutation of $\{1,2,\ldots,n\}$.

A single awakened gate is merely a lonely fracture in reality. It might carry a fleeting whisper, but it cannot bridge the void. For a continuous segment of gates to form a true path for Alice and Bob, at least two gates within it must be awakened. Only then does the space between the worlds stabilize enough for their messages to safely cross.

For any gate indices $i< j$, let $\operatorname{sec}(i,j)$ define the exact day the continuous segment of gates from $i$ to $j$ first contains at least two awakened gates. Equivalently, $\operatorname{sec}(i,j)$ is the second smallest value among $p_i,p_{i+1},\ldots,p_j$.

You are given $q$ queries. Each query is defined by an interval $[L,R]$. For each query, calculate the sum of the exact days on which every valid continuous subsegment fully contained within $[L,R]$ first becomes able to carry their messages:

$$ \sum_{L \le i < j \le R} \operatorname{sec}(i,j). $$

If $L=R$, there is no segment containing at least two gates, so the answer is $0$.

Input

The first line contains two integers $n$ and $q$ ($1 \le n,q \le 2\cdot 10^5$).

The second line contains $n$ integers $p_1,p_2,\ldots,p_n$ forming a permutation of $\{1,2,\ldots,n\}$.

Each of the next $q$ lines contains two integers $L$ and $R$ ($1 \le L \le R \le n$), describing a query.

Output

Print $q$ lines. The $t$-th line must contain the answer to the $t$-th query.

Examples

Input 1

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

Output 1

18
10
3
0

Note

For the first query, the subarrays of length at least $2$ inside $[1,4]$ have second minimums $3,3,2,4,2,4$, so the answer is $18$.