#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = double;
struct RMQ {
int n;
vector<ll> tree;
RMQ(int n) {
this->n = n;
tree = vector<ll>(4 * n);
}
void update(int i, int l, int r, int qp, ll val) {
if (l == r) {
tree[i] = val;
return;
}
int m = (l + r) / 2;
if (qp <= m) update(i * 2, l, m, qp, val);
else update(i * 2 + 1, m + 1, r, qp, val);
tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
}
void update(int qp, ll val) {
update(1, 1, n, qp, val);
}
ll query(int i, int l, int r, int ql, int qr) {
if (ql > r || l > qr) return LLONG_MAX;
if (ql <= l && r <= qr) return tree[i];
int m = (l + r) / 2;
return min(query(i * 2, l, m, ql, qr), query(i * 2 + 1, m + 1, r, ql, qr));
}
ll query(int ql, int qr) {
return query(1, 1, n, ql, qr);
}
};
int main() {
//~ ofstream cout("out.txt");
ios::sync_with_stdio(0);
cin.tie(0);
int n;
ll d;
cin >> n >> d;
vector<ll> a(n + 1);
vector<ll> ps(n + 1);
RMQ mn(n);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
ps[i] += a[i];
if (i) ps[i] += ps[i - 1];
mn.update(i, a[i]);
}
vector<int> left(n + 1, -1);
deque<int> dq;
for (int i = 1; i <= n; ++i) {
if (dq.size() && dq.back() > a[i]) while (dq.size()) dq.pop_back();
dq.push_back(a[i]);
left[i] = dq.size();
}
//~ for (int i = 1; i <= n; ++i) {
//~ cout << a[i] << " ";
//~ }
//~ cout << "\n";
//~ for (int i = 1; i <= n; ++i) {
//~ cout << left[i] << " ";
//~ }
//~ cout << "\n";
int q;
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
if (r - left[r] < l) {
cout << "0\n";
continue;
}
int i = r - left[r];
ll reduce = mn.query(l, r);
ll take = ps[i] - ps[l - 1] - reduce * (i - l + 1);
cout << take << "\n";
}
}
