Legend has it that there is a powerful Bald Chieftain at the Minsk Aerospace Agency. The Bald Chieftain possesses immense magical power; he has no hair on his head, his head is exceptionally hard, and he is quite fast at running. One day, the Peashooter arrived at the Minsk Aerospace Agency. To test this newcomer, the Bald Chieftain posed the following problem: 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, m$. The next line contains $n$ integers representing the elements of the sequence $a$. The following $m$ lines each contain two integers $l, r$ representing a query.

Output

For each query, output one integer per line representing the answer.

Constraints

• For 10% of the data, $n, m \le 10^3$;
• For another 10% of the data, $n, m \le 5 \times 10^4$;
• For another 10% of the data, $n, m \le 10^5$;
• For another 10% of the data, $n, m \le 2 \times 10^5$;
• For another 20% of the data, $|a_i - i| \le 10$;
• For another 20% of the data, $m = \frac{n(n-1)}{2}$;
• For the remaining data, there are no special restrictions.
• For 100% of the data, $1 \le n, m \le 5 \times 10^5$, $1 \le a_i \le n$, all $a_i$ are distinct, $1 \le l \le r \le n$, and all values are integers.

Examples

Input 1

5 2
5 4 2 3 1
3 4
2 5

Output 1

1
5

Note

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

For the second query, the elements in the range 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$.