Old M is a famous master of Hunyuan Xingyi Taiji. Admirers often come to seek his tutelage, but they must first pass a rigorous entrance exam: climbing stairs.

Old M's dojo has $n$ platforms arranged in a row. The height of the $i$-th platform is $h_i$, and the energy consumed to climb from the $i$-th platform to the $(i+1)$-th platform is $|h_i - h_{i+1}|$.

When the $j$-th admirer comes to seek tutelage, Old M specifies an interval $[l_j, r_j]$, takes all platforms within this interval, and uses his internal energy to rearrange them (without changing the original sequence) such that the total energy consumed to climb all the stairs is maximized. That is, he wants to calculate $\max_{p \in S} \sum_{i=l_j}^{r_j-1} |p_i - p_{i+1}|$, where $S$ is the set of all possible sequences formed by rearranging $\{h_{l_j}, h_{l_j+1}, \dots, h_{r_j}\}$. However, Old M is busy practicing MMA, so he asks you—the $992\,844\,853$-rd true disciple of the M-style Hunyuan Xingyi Taiji—to calculate this maximum value.

Input

The first line contains two positive integers $n$ and $m$, representing the number of platforms and the total number of admirers, respectively.

The second line contains $n$ positive integers $h_1 \sim h_n$, representing the heights of platforms $1 \sim n$ in order.

The next $m$ lines each contain two positive integers $l_i$ and $r_i$ ($1 \le l_i < r_i \le n$), representing a new admirer seeking tutelage. You need to answer the maximum energy consumed after rearranging the interval $[l_i, r_i]$.

Output

Output $m$ lines, where the $i$-th line contains an integer representing the maximum energy consumed by the $i$-th admirer.

Examples

Input 1

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

Output 1

2
5
4
0

Note 1

For the first query, one optimal arrangement is $[2, 3, 2]$, consuming $2$ units of energy.

For the second query, one optimal arrangement is $[3, 2, 4, 2]$, consuming $5$ units of energy.

For the third query, one optimal arrangement is $[2, 4, 2]$, consuming $4$ units of energy.

For the fourth query, one optimal arrangement is $[2, 2]$, consuming $0$ units of energy.

Constraints

Subtask 1 ($5\%$): $n, m \le 10$;

Subtask 2 ($10\%$): $h_i \le 2$;

Subtask 3 ($20\%$): $h_i \le 3$;

Subtask 4 ($25\%$): $n, m \le 2000$;

Subtask 5 ($40\%$): No additional constraints.

For all data, $2 \le n, m \le 200\,000$ and $1 \le h_i \le 10^9$.

It is guaranteed that for all queries, $1 \le l_i < r_i \le n$.