#include <bits/stdc++.h>
using namespace std;
int main() {
int n, d; cin >> n >> d;
int fish[n];
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 range[n];
int cnt = 0;
int min = 1e9;
for (int j = l - 1; j < r - 1; j++) {
if (min > fish[j]) {
min = fish[j];
}
range[cnt] = fish[j];
cnt++;
}
for (int k = 0; k < r - l; k++) {
range[k] = range[k] - min;
}
int cnt2 = 0;
int temp = r-l-1;
int prev = range[temp];
for (int i = r - l - 2; i>= 0; i--) {
if (range[i] != prev) {
cnt2++;
}
}
int sum = 0;
for (int j = 0; j < r-l-cnt2; j++) {
sum += range[j];
}
cout << sum << "\n";
}
}
