#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010, inf = 0x7f7f7f7f;
int n, q, a[maxn], bin[30], lo[10000000], st[maxn], top, size, po[maxn];
long long misaka, ans[200];
struct wtf_sequence {
  int a[maxn], mp[maxn][20];
  long long sum[maxn];
  void init() {
    top = 0;
    a[n + 1] = inf;
    sum[n + 1] = 0;
    st[++top] = n + 1;
    for (int i = n; i >= 1; i--) {
      while (a[i] > a[st[top]] && top > 0) top--;
      sum[i] = (long long)(st[top] - i) * a[i] + sum[st[top]];
      st[++top] = i;
    }
  }
  void rmqinit() {
    for (int i = 1; i <= n; i++) mp[i][0] = i;
    for (int j = 1; bin[j] <= n; j++)
      for (int i = 1; i + bin[j] - 1 <= n; i++) {
        if (a[mp[i][j - 1]] <= a[mp[i + bin[j - 1]][j - 1]])
          mp[i][j] = mp[i + bin[j - 1]][j - 1];
        else
          mp[i][j] = mp[i][j - 1];
      }
  }
  int rmqquery(int l, int r) {
    int emilia = lo[r - l + 1];
    if (a[mp[l][emilia]] <= a[mp[r - bin[emilia] + 1][emilia]])
      return mp[r - bin[emilia] + 1][emilia];
    else
      return mp[l][emilia];
  }
  void alter(int l, int r, int flag) {
    int p = rmqquery(l, r);
    misaka +=
        (long long)flag * (sum[l] - sum[p] + (long long)a[p] * (r - p + 1));
  }
} seq, qes;
struct hh {
  int l, r, id;
  long long ans;
} que[200];
bool operator<(const hh &a, const hh &b) {
  return po[a.l] == po[b.l] ? a.r < b.r : po[a.l] < po[b.l];
}
void billy() {
  int curl = que[1].l, curr = que[1].l - 1;
  for (int i = 1; i <= q; i++) {
    while (curr < que[i].r) qes.alter(n - (++curr) + 1, n - curl + 1, 1);
    while (curr > que[i].r) qes.alter(n - (curr--) + 1, n - curl + 1, -1);
    while (curl < que[i].l) seq.alter(curl++, curr, -1);
    while (curl > que[i].l) seq.alter(--curl, curr, 1);
    que[i].ans = misaka;
  }
}
int main() {
  scanf("%d", &n);
  scanf("%d", &q);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i < n; i++) seq.a[i] = abs(a[i + 1] - a[i]);
  for (int i = 1; i < n; i++) qes.a[i] = seq.a[n - i];
  n--;
  bin[0] = 1;
  for (int i = 1; i < 20; i++) bin[i] = bin[i - 1] << 1;
  for (int i = 0; bin[i] <= n; i++)
    for (int j = bin[i]; j <= bin[i + 1] - 1; j++) lo[j] = i;
  seq.init();
  seq.rmqinit();
  qes.init();
  qes.rmqinit();
  size = sqrt(q);
  for (int i = 1; i <= q; i++) {
    scanf("%d%d", &que[i].l, &que[i].r);
    que[i].id = i;
    que[i].r--;
  }
  for (int i = 1; i <= 100000; i++) po[i] = (i - 1) / size;
  sort(que + 1, que + q + 1);
  billy();
  for (int i = 1; i <= q; i++) ans[que[i].id] = que[i].ans;
  for (int i = 1; i <= q; i++) printf("%I64d\n", ans[i]);
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

A function <image> 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 <image>. We'll deal with a more... discrete version of this term.

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

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



In other words, <image> 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 <image> of size n and q queries of the form [l, r]. For each query, consider the subarray <image>; determine the sum of Lipschitz constants of all subarrays of <image>.

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 <image> and the number of queries respectively.

The second line contains n space-separated integers <image> (<image>).

The following q lines describe queries. The i-th of those lines contains two space-separated integers li and ri (1 ≤ li < ri ≤ 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 <image>.

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 <image> with length at least 2 are:

  * <image>
  * <image>
  * <image>



The answer to the query is their sum.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010, inf = 0x7f7f7f7f;
int n, q, a[maxn], bin[30], lo[10000000], st[maxn], top, size, po[maxn];
long long misaka, ans[200];
struct wtf_sequence {
  int a[maxn], mp[maxn][20];
  long long sum[maxn];
  void init() {
    top = 0;
    a[n + 1] = inf;
    sum[n + 1] = 0;
    st[++top] = n + 1;
    for (int i = n; i >= 1; i--) {
      while (a[i] > a[st[top]] && top > 0) top--;
      sum[i] = (long long)(st[top] - i) * a[i] + sum[st[top]];
      st[++top] = i;
    }
  }
  void rmqinit() {
    for (int i = 1; i <= n; i++) mp[i][0] = i;
    for (int j = 1; bin[j] <= n; j++)
      for (int i = 1; i + bin[j] - 1 <= n; i++) {
        if (a[mp[i][j - 1]] <= a[mp[i + bin[j - 1]][j - 1]])
          mp[i][j] = mp[i + bin[j - 1]][j - 1];
        else
          mp[i][j] = mp[i][j - 1];
      }
  }
  int rmqquery(int l, int r) {
    int emilia = lo[r - l + 1];
    if (a[mp[l][emilia]] <= a[mp[r - bin[emilia] + 1][emilia]])
      return mp[r - bin[emilia] + 1][emilia];
    else
      return mp[l][emilia];
  }
  void alter(int l, int r, int flag) {
    int p = rmqquery(l, r);
    misaka +=
        (long long)flag * (sum[l] - sum[p] + (long long)a[p] * (r - p + 1));
  }
} seq, qes;
struct hh {
  int l, r, id;
  long long ans;
} que[200];
bool operator<(const hh &a, const hh &b) {
  return po[a.l] == po[b.l] ? a.r < b.r : po[a.l] < po[b.l];
}
void billy() {
  int curl = que[1].l, curr = que[1].l - 1;
  for (int i = 1; i <= q; i++) {
    while (curr < que[i].r) qes.alter(n - (++curr) + 1, n - curl + 1, 1);
    while (curr > que[i].r) qes.alter(n - (curr--) + 1, n - curl + 1, -1);
    while (curl < que[i].l) seq.alter(curl++, curr, -1);
    while (curl > que[i].l) seq.alter(--curl, curr, 1);
    que[i].ans = misaka;
  }
}
int main() {
  scanf("%d", &n);
  scanf("%d", &q);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i < n; i++) seq.a[i] = abs(a[i + 1] - a[i]);
  for (int i = 1; i < n; i++) qes.a[i] = seq.a[n - i];
  n--;
  bin[0] = 1;
  for (int i = 1; i < 20; i++) bin[i] = bin[i - 1] << 1;
  for (int i = 0; bin[i] <= n; i++)
    for (int j = bin[i]; j <= bin[i + 1] - 1; j++) lo[j] = i;
  seq.init();
  seq.rmqinit();
  qes.init();
  qes.rmqinit();
  size = sqrt(q);
  for (int i = 1; i <= q; i++) {
    scanf("%d%d", &que[i].l, &que[i].r);
    que[i].id = i;
    que[i].r--;
  }
  for (int i = 1; i <= 100000; i++) po[i] = (i - 1) / size;
  sort(que + 1, que + q + 1);
  billy();
  for (int i = 1; i <= q; i++) ans[que[i].id] = que[i].ans;
  for (int i = 1; i <= q; i++) printf("%I64d\n", ans[i]);
  return 0;
}

```