# Codeforces Round #333 (Div. 1) B. Lipshitz Sequence

,

ところで、今回のこどふぉはが居る。かわいい。

## B. Lipshitz Sequence

### 問題

$$\begin{array}{ll} L(h) = 0 & (n = 1) L(h) = \max \lceil \frac{|h_j - h_i|}{j - i} \rceil & (otherwise) \end{array}$$

で定める。

### 実装

#include <iostream>
#include <vector>
#include <stack>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
typedef long long ll;
using namespace std;
struct intervals_t {
int max;
ll count;
};
int main() {
int n, q; cin >> n >> q;
vector<int> a(n); repeat (i,n) cin >> a[i];
vector<int> b(n-1); repeat (i,n-1) b[i] = abs(a[i+1] - a[i]);
repeat (qi,q) {
int l, r; cin >> l >> r; -- l; -- r; // [l, r) on b
ll result = 0;
ll acc = 0;
stack<intervals_t> stk;
repeat_from (i,l,r) {
ll cnt = 0;
while (not stk.empty() and stk.top().max <= b[i]) {
cnt += stk.top().count;
acc -= stk.top().max * stk.top().count;
stk.pop();
}
stk.push((intervals_t){ b[i], cnt + 1 });
acc += b[i] * (cnt + 1);
result += acc;
}
cout << result << endl;
}
return 0;
}