#include <bits/stdc++.h>
template <typename T>
class IntegerIterator
    : public std::iterator<std::input_iterator_tag, T, std::ptrdiff_t, T*, T> {
 public:
  explicit IntegerIterator(int value) : value(value) {}
  IntegerIterator& operator++() {
    ++value;
    return *this;
  }
  IntegerIterator operator++(int) {
    IntegerIterator copy = *this;
    ++value;
    return copy;
  }
  IntegerIterator& operator--() {
    --value;
    return *this;
  }
  IntegerIterator operator--(int) {
    IntegerIterator copy = *this;
    --value;
    return copy;
  }
  T operator*() const { return value; }
  bool operator==(IntegerIterator rhs) { return value == rhs.value; }
  bool operator!=(IntegerIterator rhs) { return !(*this == rhs); }

 private:
  T value;
};
template <typename T>
class IntegerRange {
 public:
  IntegerRange(T begin, T end) : begin_(begin), end_(end) {}
  IntegerIterator<T> begin() const { return IntegerIterator<T>(begin_); }
  IntegerIterator<T> end() const { return IntegerIterator<T>(end_); }

 private:
  T begin_;
  T end_;
};
template <typename T>
class ReversedIntegerRange {
 public:
  ReversedIntegerRange(T begin, T end) : begin_(begin), end_(end) {}
  std::reverse_iterator<IntegerIterator<T>> begin() const {
    return std::reverse_iterator<IntegerIterator<T>>(
        IntegerIterator<T>(begin_));
  }
  std::reverse_iterator<IntegerIterator<T>> end() const {
    return std::reverse_iterator<IntegerIterator<T>>(IntegerIterator<T>(end_));
  }

 private:
  T begin_;
  T end_;
};
template <typename T>
IntegerRange<T> range(T to) {
  ;
  return IntegerRange<T>(0, to);
}
template <typename T>
IntegerRange<T> range(T from, T to) {
  ;
  return IntegerRange<T>(from, to);
}
template <typename T>
IntegerRange<T> inclusiveRange(T to) {
  ;
  return IntegerRange<T>(0, to + 1);
}
template <typename T>
IntegerRange<T> inclusiveRange(T from, T to) {
  ;
  return IntegerRange<T>(from, to + 1);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from) {
  ;
  return ReversedIntegerRange<T>(from, 0);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from, T to) {
  ;
  return ReversedIntegerRange<T>(from, to);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from) {
  ;
  return ReversedIntegerRange<T>(from + 1, 0);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from, T to) {
  ;
  return ReversedIntegerRange<T>(from + 1, to);
}
using namespace std;
class TaskB {
 public:
  void solve(std::istream& in, std::ostream& out) {
    int n, q;
    in >> n >> q;
    vector<int> v(n);
    for (int i : range(n)) {
      in >> v[i];
    }
    for (int i : range(n - 1)) {
      v[i] = abs(v[i] - v[i + 1]);
      assert(v[i] < 1000000000);
    }
    v.pop_back();
    for (int ir : range(q)) {
      int l, r;
      in >> l >> r;
      --l;
      --r;
      stack<pair<int, int>> s;
      s.emplace(-1, 1000000000);
      long long sumAns = 0;
      long long sum = 0;
      for (int i : range(l, r)) {
        int curFrom = i;
        sum += v[i];
        while (v[i] >= s.top().second) {
          int len = curFrom - s.top().first;
          curFrom = s.top().first;
          sum += len * 1LL * (v[i] - s.top().second);
          s.pop();
        }
        s.emplace(curFrom, v[i]);
        sumAns += sum;
      }
      out << sumAns << "\n";
    }
  }
};
int main() {
  std::ios_base::sync_with_stdio(false);
  TaskB solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  in.tie(0);
  out << std::fixed;
  out.precision(20);
  solver.solve(in, out);
  return 0;
}

### Prompt

Your challenge is to write 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>
class IntegerIterator
    : public std::iterator<std::input_iterator_tag, T, std::ptrdiff_t, T*, T> {
 public:
  explicit IntegerIterator(int value) : value(value) {}
  IntegerIterator& operator++() {
    ++value;
    return *this;
  }
  IntegerIterator operator++(int) {
    IntegerIterator copy = *this;
    ++value;
    return copy;
  }
  IntegerIterator& operator--() {
    --value;
    return *this;
  }
  IntegerIterator operator--(int) {
    IntegerIterator copy = *this;
    --value;
    return copy;
  }
  T operator*() const { return value; }
  bool operator==(IntegerIterator rhs) { return value == rhs.value; }
  bool operator!=(IntegerIterator rhs) { return !(*this == rhs); }

 private:
  T value;
};
template <typename T>
class IntegerRange {
 public:
  IntegerRange(T begin, T end) : begin_(begin), end_(end) {}
  IntegerIterator<T> begin() const { return IntegerIterator<T>(begin_); }
  IntegerIterator<T> end() const { return IntegerIterator<T>(end_); }

 private:
  T begin_;
  T end_;
};
template <typename T>
class ReversedIntegerRange {
 public:
  ReversedIntegerRange(T begin, T end) : begin_(begin), end_(end) {}
  std::reverse_iterator<IntegerIterator<T>> begin() const {
    return std::reverse_iterator<IntegerIterator<T>>(
        IntegerIterator<T>(begin_));
  }
  std::reverse_iterator<IntegerIterator<T>> end() const {
    return std::reverse_iterator<IntegerIterator<T>>(IntegerIterator<T>(end_));
  }

 private:
  T begin_;
  T end_;
};
template <typename T>
IntegerRange<T> range(T to) {
  ;
  return IntegerRange<T>(0, to);
}
template <typename T>
IntegerRange<T> range(T from, T to) {
  ;
  return IntegerRange<T>(from, to);
}
template <typename T>
IntegerRange<T> inclusiveRange(T to) {
  ;
  return IntegerRange<T>(0, to + 1);
}
template <typename T>
IntegerRange<T> inclusiveRange(T from, T to) {
  ;
  return IntegerRange<T>(from, to + 1);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from) {
  ;
  return ReversedIntegerRange<T>(from, 0);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from, T to) {
  ;
  return ReversedIntegerRange<T>(from, to);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from) {
  ;
  return ReversedIntegerRange<T>(from + 1, 0);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from, T to) {
  ;
  return ReversedIntegerRange<T>(from + 1, to);
}
using namespace std;
class TaskB {
 public:
  void solve(std::istream& in, std::ostream& out) {
    int n, q;
    in >> n >> q;
    vector<int> v(n);
    for (int i : range(n)) {
      in >> v[i];
    }
    for (int i : range(n - 1)) {
      v[i] = abs(v[i] - v[i + 1]);
      assert(v[i] < 1000000000);
    }
    v.pop_back();
    for (int ir : range(q)) {
      int l, r;
      in >> l >> r;
      --l;
      --r;
      stack<pair<int, int>> s;
      s.emplace(-1, 1000000000);
      long long sumAns = 0;
      long long sum = 0;
      for (int i : range(l, r)) {
        int curFrom = i;
        sum += v[i];
        while (v[i] >= s.top().second) {
          int len = curFrom - s.top().first;
          curFrom = s.top().first;
          sum += len * 1LL * (v[i] - s.top().second);
          s.pop();
        }
        s.emplace(curFrom, v[i]);
        sumAns += sum;
      }
      out << sumAns << "\n";
    }
  }
};
int main() {
  std::ios_base::sync_with_stdio(false);
  TaskB solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  in.tie(0);
  out << std::fixed;
  out.precision(20);
  solver.solve(in, out);
  return 0;
}

```