Given $n$ numbers $a_1, \dots, a_n$.

A pair $(x, y)$ is called a "good pair" if for all $i = 1, 2, \dots, n$ such that $i \neq x$, the condition $|a_x - a_y| \le |a_x - a_i|$ holds.

You are given several queries. For each query $[l, r]$, count how many good pairs $(x, y)$ exist such that $l \le x, y \le r$ and $x \neq y$.

Input

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

The second line contains $n$ integers $a_1, \dots, a_n$.

The next $m$ lines each contain two integers $l$ and $r$.

Output

Let $Ans_i$ be the answer to the $i$-th query. Output $\sum_{i=1}^m Ans_i \times i$.

Examples

Input 1

3 2
2 1 3
1 2
1 3

Output 1

10

Subtasks

For $20\%$ of the data, $n, m \le 300$.

For $40\%$ of the data, $n, m \le 5\,000$.

For $70\%$ of the data, $n, m \le 50\,000$.

For $100\%$ of the data, $1 \le n, m \le 3 \times 10^5$, $1 \le a_i \le 10^9$, $1 \le l \le r \le n$, and $a_i \neq a_j$ for all $i \neq j$.