#include <bits/stdc++.h>
template <typename T>
inline T abs(T a) {
  return a < 0 ? -a : a;
}
template <typename T>
inline T min(T a, T b) {
  return a < b ? a : b;
}
template <typename T>
inline T max(T a, T b) {
  return a > b ? a : b;
}
template <typename T>
inline void swap(T& a, T& b) {
  T t = a;
  a = b, b = t;
}
template <typename T>
inline bool umin(T& mn, T u) {
  return u < mn ? mn = u, true : false;
}
template <typename T>
inline bool umax(T& mx, T u) {
  return u > mx ? mx = u, true : false;
}
template <typename T>
inline void read(T& r) {
  char c;
  r = 0;
  bool flag = false;
  do c = getchar();
  while (c != '-' && (c < '0' || c > '9'));
  if (c == '-') flag = true, c = getchar();
  do r = r * 10 + c - '0', c = getchar();
  while (c >= '0' && c <= '9');
  if (flag) r *= -1;
}
template <typename T1, typename T2>
inline void read(T1& r, T2& s) {
  read(r), read(s);
}
template <typename T1, typename T2, typename T3>
inline void read(T1& r, T2& s, T3& t) {
  read(r), read(s), read(t);
}
template <typename T1, typename T2, typename T3, typename T4>
inline void read(T1& r, T2& s, T3& t, T4& u) {
  read(r), read(s), read(t), read(u);
}
template <typename T>
inline void write(T w, const char* c = "") {
  if (w == 0)
    putchar('0');
  else {
    if (w < 0) putchar('-'), w *= -1;
    static int s[21], top;
    top = 0;
    while (w) s[top++] = w % 10, w /= 10;
    while (top--) putchar(s[top] + '0');
  }
  for (int i = 0; c[i]; i++) putchar(c[i]);
}
inline std::pair<int, int> max(std::pair<int, int> a, std::pair<int, int> b) {
  return a.first > b.first ? a : b;
}
int a[100000], lg[100001], n;
std::pair<int, int> st[100001][17];
void init() {
  int i, j, k, maxlog;
  for (i = 0, j = 0, k = 2; i <= n; i++) lg[i] = i < k ? j : (k <<= 1, ++j);
  maxlog = lg[n];
  for (i = 0; i < n; i++) st[i][0] = std::pair<int, int>(a[i], i);
  for (k = 0; k < maxlog; k++)
    for (i = 0; i + (1 << (k + 1)) <= n; i++)
      st[i][k + 1] = max(st[i][k], st[i + (1 << k)][k]);
}
std::pair<int, int> query(int l, int r) {
  int d = lg[r - l + 1];
  return max(st[l][d], st[r - (1 << d) + 1][d]);
}
long long ans;
void getans(int l, int r) {
  if (l > r) return;
  std::pair<int, int> mx = query(l, r);
  int pos = mx.second;
  ans += (long long)(pos - l + 1) * (r - pos + 1) * mx.first;
  getans(l, pos - 1);
  getans(pos + 1, r);
}
int main() {
  int m, i, l, r;
  read(n, m);
  for (i = 0; i < n; i++) read(a[i]);
  for (i = 1; i < n; i++) a[i - 1] = abs(a[i - 1] - a[i]);
  n--;
  init();
  while (m--) {
    read(l, r), l--, r -= 2;
    ans = 0, getans(l, r);
    write(ans, "\n");
  }
  return 0;
}

### Prompt

Generate a Cpp solution to the following problem:

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>
template <typename T>
inline T abs(T a) {
  return a < 0 ? -a : a;
}
template <typename T>
inline T min(T a, T b) {
  return a < b ? a : b;
}
template <typename T>
inline T max(T a, T b) {
  return a > b ? a : b;
}
template <typename T>
inline void swap(T& a, T& b) {
  T t = a;
  a = b, b = t;
}
template <typename T>
inline bool umin(T& mn, T u) {
  return u < mn ? mn = u, true : false;
}
template <typename T>
inline bool umax(T& mx, T u) {
  return u > mx ? mx = u, true : false;
}
template <typename T>
inline void read(T& r) {
  char c;
  r = 0;
  bool flag = false;
  do c = getchar();
  while (c != '-' && (c < '0' || c > '9'));
  if (c == '-') flag = true, c = getchar();
  do r = r * 10 + c - '0', c = getchar();
  while (c >= '0' && c <= '9');
  if (flag) r *= -1;
}
template <typename T1, typename T2>
inline void read(T1& r, T2& s) {
  read(r), read(s);
}
template <typename T1, typename T2, typename T3>
inline void read(T1& r, T2& s, T3& t) {
  read(r), read(s), read(t);
}
template <typename T1, typename T2, typename T3, typename T4>
inline void read(T1& r, T2& s, T3& t, T4& u) {
  read(r), read(s), read(t), read(u);
}
template <typename T>
inline void write(T w, const char* c = "") {
  if (w == 0)
    putchar('0');
  else {
    if (w < 0) putchar('-'), w *= -1;
    static int s[21], top;
    top = 0;
    while (w) s[top++] = w % 10, w /= 10;
    while (top--) putchar(s[top] + '0');
  }
  for (int i = 0; c[i]; i++) putchar(c[i]);
}
inline std::pair<int, int> max(std::pair<int, int> a, std::pair<int, int> b) {
  return a.first > b.first ? a : b;
}
int a[100000], lg[100001], n;
std::pair<int, int> st[100001][17];
void init() {
  int i, j, k, maxlog;
  for (i = 0, j = 0, k = 2; i <= n; i++) lg[i] = i < k ? j : (k <<= 1, ++j);
  maxlog = lg[n];
  for (i = 0; i < n; i++) st[i][0] = std::pair<int, int>(a[i], i);
  for (k = 0; k < maxlog; k++)
    for (i = 0; i + (1 << (k + 1)) <= n; i++)
      st[i][k + 1] = max(st[i][k], st[i + (1 << k)][k]);
}
std::pair<int, int> query(int l, int r) {
  int d = lg[r - l + 1];
  return max(st[l][d], st[r - (1 << d) + 1][d]);
}
long long ans;
void getans(int l, int r) {
  if (l > r) return;
  std::pair<int, int> mx = query(l, r);
  int pos = mx.second;
  ans += (long long)(pos - l + 1) * (r - pos + 1) * mx.first;
  getans(l, pos - 1);
  getans(pos + 1, r);
}
int main() {
  int m, i, l, r;
  read(n, m);
  for (i = 0; i < n; i++) read(a[i]);
  for (i = 1; i < n; i++) a[i - 1] = abs(a[i - 1] - a[i]);
  n--;
  init();
  while (m--) {
    read(l, r), l--, r -= 2;
    ans = 0, getans(l, r);
    write(ans, "\n");
  }
  return 0;
}

```