#include <bits/stdc++.h>
#pragma GCC optimize(1)
#pragma G++ optimize(1)
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#pragma GCC optimize(3)
#pragma G++ optimize(3)
#pragma GCC optimize(4)
#pragma G++ optimize(4)
#pragma GCC optimize(5)
#pragma G++ optimize(5)
#pragma GCC optimize(6)
#pragma G++ optimize(6)
#pragma GCC optimize(7)
#pragma G++ optimize(7)
#pragma GCC optimize(8)
#pragma G++ optimize(8)
#pragma GCC optimize(9)
#pragma G++ optimize(9)
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
using namespace std;
const int INF = 2147483647;
const double PI = 3.1415926535897932384626;
const int maxn = 10005;
struct bign {
  int d[maxn], len;
  inline void clean() {
    while (len > 1 && !d[len - 1]) len--;
  }
  inline bign() {
    memset(d, 0, sizeof(d));
    len = 1;
  }
  inline bign(int num) { *this = num; }
  inline bign(char* num) { *this = num; }
  inline bign operator=(const char* num) {
    memset(d, 0, sizeof(d));
    len = strlen(num);
    for (int i = 0; i < len; i++) d[i] = num[len - 1 - i] - '0';
    clean();
    return *this;
  }
  inline bign operator=(int num) {
    char s[20];
    sprintf(s, "%d", num);
    *this = s;
    return *this;
  }
  inline bign operator+(const bign& b) {
    bign c = *this;
    int i;
    for (i = 0; i < b.len; i++) {
      c.d[i] += b.d[i];
      if (c.d[i] > 9) c.d[i] %= 10, c.d[i + 1]++;
    }
    while (c.d[i] > 9) c.d[i++] %= 10, c.d[i]++;
    c.len = max(len, b.len);
    if (c.d[i] && c.len <= i) c.len = i + 1;
    return c;
  }
  inline bign operator-(const bign& b) {
    bign c = *this;
    int i;
    for (i = 0; i < b.len; i++) {
      c.d[i] -= b.d[i];
      if (c.d[i] < 0) c.d[i] += 10, c.d[i + 1]--;
    }
    while (c.d[i] < 0) c.d[i++] += 10, c.d[i]--;
    for (i = c.len - 1; i > 0; i--)
      if (c.d[i] != 0) break;
    c.len = i + 1;
    return c;
  }
  inline bign operator*(const bign& b) const {
    int i, j;
    bign c;
    c.len = len + b.len;
    for (j = 0; j < b.len; j++)
      for (i = 0; i < len; i++) c.d[i + j] += d[i] * b.d[j];
    for (i = 0; i < c.len - 1; i++) c.d[i + 1] += c.d[i] / 10, c.d[i] %= 10;
    c.clean();
    return c;
  }
  inline bign operator/(const bign& b) {
    int i, j;
    bign c = *this, a = 0;
    for (i = len - 1; i >= 0; i--) {
      a = a * 10 + d[i];
      for (j = 0; j < 10; j++)
        if (a < b * (j + 1)) break;
      c.d[i] = j;
      a = a - b * j;
    }
    c.clean();
    return c;
  }
  inline bign operator%(const bign& b) {
    int i, j;
    bign a = 0;
    for (i = len - 1; i >= 0; i--) {
      a = a * 10 + d[i];
      for (j = 0; j < 10; j++)
        if (a < b * (j + 1)) break;
      a = a - b * j;
    }
    return a;
  }
  inline bign operator+=(const bign& b) {
    *this = *this + b;
    return *this;
  }
  inline bign operator*=(const bign& b) {
    *this = *this * b;
    return *this;
  }
  inline bign operator-=(const bign& b) {
    *this = *this - b;
    return *this;
  }
  inline bign operator/=(const bign& b) {
    *this = *this / b;
    return *this;
  }
  inline bool operator<(const bign& b) const {
    if (len != b.len) return len < b.len;
    for (int i = len - 1; i >= 0; i--)
      if (d[i] != b.d[i]) return d[i] < b.d[i];
    return false;
  }
  inline bool operator>(const bign& b) const { return b < *this; }
  inline bool operator<=(const bign& b) const { return !(b < *this); }
  inline bool operator>=(const bign& b) const { return !(*this < b); }
  inline bool operator!=(const bign& b) const { return b < *this || *this < b; }
  inline bool operator==(const bign& b) const {
    return !(b < *this) && !(b > *this);
  }
  inline string str() const {
    char s[maxn] = {};
    for (int i = 0; i < len; i++) s[len - 1 - i] = d[i] + '0';
    return s;
  }
};
inline istream& operator>>(istream& in, bign& x) {
  string s;
  in >> s;
  x = s.c_str();
  return in;
}
inline ostream& operator<<(ostream& out, const bign& x) {
  out << x.str();
  return out;
}
inline void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
inline int pt(int a[], int l, int r) {
  int p, i, j;
  p = a[l];
  i = l;
  j = r + 1;
  for (;;) {
    while (a[++i] < p)
      if (i >= r) break;
    while (a[--j] > p)
      if (j <= l) break;
    if (i >= j)
      break;
    else
      swap(a[i], a[j]);
  }
  if (j == l) return j;
  swap(a[l], a[j]);
  return j;
}
inline void q_sort(int a[], int l, int r) {
  int q;
  if (r > l) {
    q = pt(a, l, r);
    q_sort(a, l, q - 1);
    q_sort(a, q + 1, r);
  }
}
inline void write(int x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
inline void rd(long long& val) {
  long long x = 0;
  int f = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  val = x * f;
}
inline void rd(int& val) {
  int x = 0;
  int f = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  val = x * f;
}
inline void _write(int x) {
  write(x);
  putchar(' ');
}
inline void print(int x) {
  write(x);
  putchar('\n');
}
inline void _write(long long x) {
  write(x);
  putchar(' ');
}
inline void print(long long x) {
  write(x);
  putchar('\n');
}
struct PII {
  int first, second;
  PII() {}
  PII(int f, int s) : first(f), second(s) {}
  inline bool operator<(const PII& x) const {
    if (first != x.first) return first < x.first;
    return second < x.second;
  }
  inline bool operator==(const PII& x) const {
    return first == x.first and second == x.second;
  }
  inline bool operator>(const PII& x) const {
    if (first != x.first) return first > x.first;
    return second > x.second;
  }
  inline bool operator!=(const PII& x) const {
    return first != x.first and second != x.second;
  }
};
clock_t __stt;
inline void TStart() { __stt = clock(); }
inline void TReport() {
  printf("\nTaken Time : %.3lf sec\n",
         (double)(clock() - __stt) / CLOCKS_PER_SEC);
}
PII que[111111], pii[111111];
set<int> s;
int n, q, a[111111], b[111111];
long long ans[111111];
int main() {
  ios_base::sync_with_stdio(false);
  int i, j, P, Q;
  rd(n), rd(q);
  for (i = 1; i <= n; ++i) rd(a[i]);
  for (i = 1; i < n; ++i) b[i] = abs(a[i] - a[i + 1]);
  for (i = 1; i < n; ++i) pii[i] = PII(b[i], i);
  sort(pii + 1, pii + n);
  s.insert(0), s.insert(n);
  for (i = 1; i <= q; ++i) rd(que[i].first), rd(que[i].second);
  for (i = n - 1; i; --i) {
    P = pii[i].first;
    Q = pii[i].second;
    set<int>::iterator it = s.upper_bound(Q);
    int r(*it), l(*(--it) + 1);
    s.insert(Q);
    for (j = 1; j <= q; ++j) {
      int tl(max(l, que[j].first)), tr(min(r, que[j].second));
      if (tl <= Q and Q < tr)
        ans[j] += (long long)((long long)(Q - tl + 1) * (long long)(tr - Q) *
                              (long long)P);
    }
  }
  for (i = 1; i <= q; ++i) print(ans[i]);
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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>
#pragma GCC optimize(1)
#pragma G++ optimize(1)
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#pragma GCC optimize(3)
#pragma G++ optimize(3)
#pragma GCC optimize(4)
#pragma G++ optimize(4)
#pragma GCC optimize(5)
#pragma G++ optimize(5)
#pragma GCC optimize(6)
#pragma G++ optimize(6)
#pragma GCC optimize(7)
#pragma G++ optimize(7)
#pragma GCC optimize(8)
#pragma G++ optimize(8)
#pragma GCC optimize(9)
#pragma G++ optimize(9)
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
using namespace std;
const int INF = 2147483647;
const double PI = 3.1415926535897932384626;
const int maxn = 10005;
struct bign {
  int d[maxn], len;
  inline void clean() {
    while (len > 1 && !d[len - 1]) len--;
  }
  inline bign() {
    memset(d, 0, sizeof(d));
    len = 1;
  }
  inline bign(int num) { *this = num; }
  inline bign(char* num) { *this = num; }
  inline bign operator=(const char* num) {
    memset(d, 0, sizeof(d));
    len = strlen(num);
    for (int i = 0; i < len; i++) d[i] = num[len - 1 - i] - '0';
    clean();
    return *this;
  }
  inline bign operator=(int num) {
    char s[20];
    sprintf(s, "%d", num);
    *this = s;
    return *this;
  }
  inline bign operator+(const bign& b) {
    bign c = *this;
    int i;
    for (i = 0; i < b.len; i++) {
      c.d[i] += b.d[i];
      if (c.d[i] > 9) c.d[i] %= 10, c.d[i + 1]++;
    }
    while (c.d[i] > 9) c.d[i++] %= 10, c.d[i]++;
    c.len = max(len, b.len);
    if (c.d[i] && c.len <= i) c.len = i + 1;
    return c;
  }
  inline bign operator-(const bign& b) {
    bign c = *this;
    int i;
    for (i = 0; i < b.len; i++) {
      c.d[i] -= b.d[i];
      if (c.d[i] < 0) c.d[i] += 10, c.d[i + 1]--;
    }
    while (c.d[i] < 0) c.d[i++] += 10, c.d[i]--;
    for (i = c.len - 1; i > 0; i--)
      if (c.d[i] != 0) break;
    c.len = i + 1;
    return c;
  }
  inline bign operator*(const bign& b) const {
    int i, j;
    bign c;
    c.len = len + b.len;
    for (j = 0; j < b.len; j++)
      for (i = 0; i < len; i++) c.d[i + j] += d[i] * b.d[j];
    for (i = 0; i < c.len - 1; i++) c.d[i + 1] += c.d[i] / 10, c.d[i] %= 10;
    c.clean();
    return c;
  }
  inline bign operator/(const bign& b) {
    int i, j;
    bign c = *this, a = 0;
    for (i = len - 1; i >= 0; i--) {
      a = a * 10 + d[i];
      for (j = 0; j < 10; j++)
        if (a < b * (j + 1)) break;
      c.d[i] = j;
      a = a - b * j;
    }
    c.clean();
    return c;
  }
  inline bign operator%(const bign& b) {
    int i, j;
    bign a = 0;
    for (i = len - 1; i >= 0; i--) {
      a = a * 10 + d[i];
      for (j = 0; j < 10; j++)
        if (a < b * (j + 1)) break;
      a = a - b * j;
    }
    return a;
  }
  inline bign operator+=(const bign& b) {
    *this = *this + b;
    return *this;
  }
  inline bign operator*=(const bign& b) {
    *this = *this * b;
    return *this;
  }
  inline bign operator-=(const bign& b) {
    *this = *this - b;
    return *this;
  }
  inline bign operator/=(const bign& b) {
    *this = *this / b;
    return *this;
  }
  inline bool operator<(const bign& b) const {
    if (len != b.len) return len < b.len;
    for (int i = len - 1; i >= 0; i--)
      if (d[i] != b.d[i]) return d[i] < b.d[i];
    return false;
  }
  inline bool operator>(const bign& b) const { return b < *this; }
  inline bool operator<=(const bign& b) const { return !(b < *this); }
  inline bool operator>=(const bign& b) const { return !(*this < b); }
  inline bool operator!=(const bign& b) const { return b < *this || *this < b; }
  inline bool operator==(const bign& b) const {
    return !(b < *this) && !(b > *this);
  }
  inline string str() const {
    char s[maxn] = {};
    for (int i = 0; i < len; i++) s[len - 1 - i] = d[i] + '0';
    return s;
  }
};
inline istream& operator>>(istream& in, bign& x) {
  string s;
  in >> s;
  x = s.c_str();
  return in;
}
inline ostream& operator<<(ostream& out, const bign& x) {
  out << x.str();
  return out;
}
inline void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
inline int pt(int a[], int l, int r) {
  int p, i, j;
  p = a[l];
  i = l;
  j = r + 1;
  for (;;) {
    while (a[++i] < p)
      if (i >= r) break;
    while (a[--j] > p)
      if (j <= l) break;
    if (i >= j)
      break;
    else
      swap(a[i], a[j]);
  }
  if (j == l) return j;
  swap(a[l], a[j]);
  return j;
}
inline void q_sort(int a[], int l, int r) {
  int q;
  if (r > l) {
    q = pt(a, l, r);
    q_sort(a, l, q - 1);
    q_sort(a, q + 1, r);
  }
}
inline void write(int x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
inline void rd(long long& val) {
  long long x = 0;
  int f = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  val = x * f;
}
inline void rd(int& val) {
  int x = 0;
  int f = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  val = x * f;
}
inline void _write(int x) {
  write(x);
  putchar(' ');
}
inline void print(int x) {
  write(x);
  putchar('\n');
}
inline void _write(long long x) {
  write(x);
  putchar(' ');
}
inline void print(long long x) {
  write(x);
  putchar('\n');
}
struct PII {
  int first, second;
  PII() {}
  PII(int f, int s) : first(f), second(s) {}
  inline bool operator<(const PII& x) const {
    if (first != x.first) return first < x.first;
    return second < x.second;
  }
  inline bool operator==(const PII& x) const {
    return first == x.first and second == x.second;
  }
  inline bool operator>(const PII& x) const {
    if (first != x.first) return first > x.first;
    return second > x.second;
  }
  inline bool operator!=(const PII& x) const {
    return first != x.first and second != x.second;
  }
};
clock_t __stt;
inline void TStart() { __stt = clock(); }
inline void TReport() {
  printf("\nTaken Time : %.3lf sec\n",
         (double)(clock() - __stt) / CLOCKS_PER_SEC);
}
PII que[111111], pii[111111];
set<int> s;
int n, q, a[111111], b[111111];
long long ans[111111];
int main() {
  ios_base::sync_with_stdio(false);
  int i, j, P, Q;
  rd(n), rd(q);
  for (i = 1; i <= n; ++i) rd(a[i]);
  for (i = 1; i < n; ++i) b[i] = abs(a[i] - a[i + 1]);
  for (i = 1; i < n; ++i) pii[i] = PII(b[i], i);
  sort(pii + 1, pii + n);
  s.insert(0), s.insert(n);
  for (i = 1; i <= q; ++i) rd(que[i].first), rd(que[i].second);
  for (i = n - 1; i; --i) {
    P = pii[i].first;
    Q = pii[i].second;
    set<int>::iterator it = s.upper_bound(Q);
    int r(*it), l(*(--it) + 1);
    s.insert(Q);
    for (j = 1; j <= q; ++j) {
      int tl(max(l, que[j].first)), tr(min(r, que[j].second));
      if (tl <= Q and Q < tr)
        ans[j] += (long long)((long long)(Q - tl + 1) * (long long)(tr - Q) *
                              (long long)P);
    }
  }
  for (i = 1; i <= q; ++i) print(ans[i]);
}

```