// UUID: 58aa4312-42b8-4cff-86d7-75d99f849374
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 300'001;
const ll INF = 1e16;
struct segtree {
vector<ll> tree;
int n;
segtree(int n) : n(n) {
tree.resize(2*n);
}
void upd(int u, ll k) {
tree[u += n] = k;
for (u /= 2; u >= 1; u /= 2) {
tree[u] = tree[2*u] + tree[2*u+1];
}
}
ll qry(int l, int r) {
l += n; r += n;
ll res = 0;
while (l <= r) {
if (l % 2 == 1) res += tree[l++];
if (r % 2 == 0) res += tree[r--];
l /= 2; r /= 2;
}
return res;
}
};
ll c[MAXN], ans[MAXN], pref[MAXN], bef[MAXN];
vector<pair<ll, ll>> qrys[MAXN];
void solve() {
ll n, d; cin >> n >> d;
for (int i = 1; i <= n; i++) cin >> c[i];
partial_sum(c, c+MAXN, pref);
int q; cin >> q;
for (int i = 1; i <= q; i++) {
int l, r; cin >> l >> r;
qrys[r].emplace_back(l, i);
}
c[0] = -INF;
stack<ll> st;
st.push(0);
segtree tree(n+1);
set<int> pos;
for (ll i = 1; i <= n; i++) {
while (!st.empty() && c[st.top()] >= c[i]) {
tree.upd(st.top(), 0);
pos.erase(st.top());
st.pop();
}
ll j = st.top();
bef[i] = j;
st.push(i);
pos.insert(i);
tree.upd(i, (i-j)*c[i]);
for (auto [l, idx] : qrys[i]) {
ll p = *pos.lower_bound(l);
ll res = pref[i] - pref[l-1] - tree.qry(p+1, i);
res -= c[p] * (p-l+1);
ans[idx] = res;
}
}
for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
