#include <bits/stdc++.h>
const int N = 3e5 + 5;
struct segtree{
int64_t t[4*N] = {0};
int64_t query(int v, int tl, int tr, int l, int r) {
if(tl > r || tr < l) {
return 0;
}
if(tl >= l && tr <= r) {
return t[v];
}
int tm = (tl + tr) / 2;
return (query(v * 2, tl, tm, l, r) + query(v * 2 + 1, tm + 1, tr, l, r));
}
void update(int v, int tl, int tr, int index, int64_t value) {
if(tl == tr) {
t[v] = value;
}
else {
int tm = (tl + tr) / 2;
if(index <= tm) {
update(v * 2, tl, tm, index, value);
}
else {
update(v * 2 + 1, tm + 1, tr, index, value);
}
t[v] = (t[v * 2] + t[v * 2 + 1]);
}
}
}seg;
void solve() {
int n, d;
std::cin >> n >> d;
std::vector<int64_t> a(n + 1);
for(int i = 1; i <= n; i++) {
std::cin >> a[i];
}
assert(d == 1);
for(int i = 2; i <= n; i++) {
if(a[i] < a[i - 1]) {
seg.update(1, 1, n, i, a[i - 1] - a[i]);
}
}
int q;
std::cin >> q;
while(q--) {
int l, r;
std::cin >> l >> r;
std::cout << seg.query(1, 1, n, l + 1, r) << "\n";
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t = 1;
//std::cin >> t;
while (t--) {
solve();
}
return 0;
}
