#include <bits/stdc++.h>
using namespace std;
#define int long long
int fish[300005];
int range[300005];
int32_t main() {
int n, d; cin >> n >> d;
for (int i = 0; i < n; i++) {
int c; cin >> c; fish[i] = c;
}
int q; cin >> q;
while (q--) {
int l, r; cin >> l >> r;
int cnt = 0;
int min1 = 1e9;
for (int j = l - 1; j < r; j++) {
if (min1 > fish[j]) {
min1 = fish[j];
}
range[cnt] = fish[j];
cnt++;
}
for (int k = 0; k < r - l + 1; k++) {
range[k] = range[k] - min1;
}
int cnt2 = 1;
int temp = r-l;
int prev = range[temp];
for (int i = temp - 1; i>= 0; i--) {
if (range[i] == prev) {
cnt2++;
} else {
break;
}
}
int sum = 0;
for (int j = 0; j < r-l+1-cnt2; j++) {
sum += range[j];
}
cout << sum << "\n";
}
}
