Given a permutation $a_1, \dots, a_n$ of length $n$, there are $m$ queries. Each query asks for the sum of the absolute differences of the positions in the original sequence of adjacent elements after sorting the elements in the range $[l, r]$.

Input

The first line contains two integers $n$ and $m$.

The next line contains $n$ integers representing the elements of the sequence $a$.

The next $m$ lines each contain two integers $l$ and $r$, representing a query.

Output

For each query, output a single integer representing the answer on a new line.

Examples

Input 1

5 2
5 4 2 3 1
3 4
2 5

Output 1

1
5

Note 1

For the first query, the elements are $2, 3$. After sorting, they are $2, 3$. Their positions in the original sequence are $3$ and $4$. The sum of the absolute differences of the positions of adjacent elements is $|3 - 4| = 1$.

For the second query, the elements are $4, 2, 3, 1$. After sorting, they are $1, 2, 3, 4$. Their positions in the original sequence are $5, 3, 4, 2$. The sum of the absolute differences of the positions of adjacent elements is $|5 - 3| + |3 - 4| + |4 - 2| = 5$.

Subtasks

Idea: ?, Solution: ccz181078, Code: nalemy, Data: ccz181078

For $100\%$ of the data, $1 \leq n, m \leq 2\times 10^6$, $1 \leq a_i \leq n$, all $a_i$ are distinct, and $1 \leq l \leq r \leq n$. All values are integers.