#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxn = 3e5 + 5;
int n, d;
int a[mxn];
int pfx[mxn];
pair<int, int> up[mxn][20];
vector<pair<int, int>> tmp;
int sum(int l, int r) {
if (r < l) return (int)0;
return pfx[r] - pfx[l - 1];
}
int pre[mxn];
void build() {
sort(tmp.begin(), tmp.end());
set<int> add;
for (auto &x : tmp) {
int v = x.first, i = x.second;
if (!add.size()) {
pre[i] = (int)0;
add.insert(-i);
continue;
}
if (-*add.rbegin() > i) {
pre[i] = (int)0;
add.insert(-i);
continue;
}
pre[i] = -(*add.lower_bound(-i));
add.insert(-i);
}
}
signed main() {
cout.tie(nullptr); cin.tie(nullptr); ios::sync_with_stdio(false);
cin >> n >> d;
for (int i = 1; i <= n; i++) {cin >> a[i]; tmp.push_back({a[i], i});}
build(); for (int i = 1; i <= n; i++) pfx[i] = pfx[i - 1] + a[i];
// for (int i = 1; i <= n; i++) cout << pre[i] << " ";
// cout << '\n';
for (int i = 1; i <= n; i++) up[i][0] = {pre[i], sum(pre[i] + 1, i) - (i - pre[i]) * a[i]};
for (int j = 1; j < 20; j++) {
for (int i = 1; i <= n; i++) {
up[i][j] = {up[up[i][j - 1].first][j - 1].first, up[i][j - 1].second + up[up[i][j - 1].first][j - 1].second};
}
}
// for (int i = 1; i <= n; i++) {
// cout << sum(pre[i] + 1, i) << " - " << (i - pre[i]) * a[i] << '\n';
// cout << up[i][0].fi << " -> " << i << ": " << up[i][0].se << '\n';
// }
int q; cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
int sm = 0; int curr = r;
for (int i = 19; i >= 0; i--) {
if (up[curr][i].first >= l) {
sm += up[curr][i].second;
curr = up[curr][i].first;
}
}
sm += sum(l, curr) - (curr - l + 1) * a[curr];
cout << sm << '\n';
}
}
