Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

No tag edit access

B. Lipshitz Sequence

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA function is called Lipschitz continuous if there is a real constant *K* such that the inequality |*f*(*x*) - *f*(*y*)| ≤ *K*·|*x* - *y*| holds for all . We'll deal with a more... discrete version of this term.

For an array , we define it's Lipschitz constant as follows:

- if
*n*< 2, - if
*n*≥ 2, over all 1 ≤*i*<*j*≤*n*

In other words, is the smallest non-negative integer such that |*h*[*i*] - *h*[*j*]| ≤ *L*·|*i* - *j*| holds for all 1 ≤ *i*, *j* ≤ *n*.

You are given an array of size *n* and *q* queries of the form [*l*, *r*]. For each query, consider the subarray ; determine the sum of Lipschitz constants of all subarrays of .

Input

The first line of the input contains two space-separated integers *n* and *q* (2 ≤ *n* ≤ 100 000 and 1 ≤ *q* ≤ 100) — the number of elements in array and the number of queries respectively.

The second line contains *n* space-separated integers ().

The following *q* lines describe queries. The *i*-th of those lines contains two space-separated integers *l*_{i} and *r*_{i} (1 ≤ *l*_{i} < *r*_{i} ≤ *n*).

Output

Print the answers to all queries in the order in which they are given in the input. For the *i*-th query, print one line containing a single integer — the sum of Lipschitz constants of all subarrays of .

Examples

Input

10 4

1 5 2 9 1 3 4 2 1 7

2 4

3 8

7 10

1 9

Output

17

82

23

210

Input

7 6

5 7 7 4 6 6 2

1 2

2 3

2 6

1 7

4 7

3 5

Output

2

0

22

59

16

8

Note

In the first query of the first sample, the Lipschitz constants of subarrays of with length at least 2 are:

The answer to the query is their sum.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/16/2018 01:03:06 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|