#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = double;
const int MAXN = 3e5;
ll d;
struct LazySeg {
int n;
struct Node {
ll sumD, mnH, lz;
Node() {
sumD = mnH = lz = 0;
}
Node friend operator + (const Node& lhs, const Node& rhs) {
Node res;
res.sumD = lhs.sumD + rhs.sumD;
res.mnH = min(lhs.mnH, rhs.mnH);
return res;
}
};
void init(int n) {
this->n = n;
}
Node tree[4 * MAXN + 1];
void push(int i, int l, int r) {
if (tree[i].lz == 0) {
return;
}
tree[i].sumD += tree[i].lz * (r - l + 1);
tree[i].mnH -= d * tree[i].lz;
if (l < r) {
tree[i * 2].lz += tree[i].lz;
tree[i * 2 + 1].lz += tree[i].lz;
}
tree[i].lz = 0;
}
void activate(int i, int l, int r, int qp, ll val) {
//~ cerr << "at index = " << i << " , with bounds = [" << l << " , " << r << "]\n";
push(i, l, r);
if (l == r) {
tree[i].mnH = val;
return;
}
int m = (l + r) / 2;
if (qp <= m) activate(i * 2, l, m, qp, val);
else activate(i * 2 + 1, m + 1, r, qp, val);
tree[i] = tree[i * 2] + tree[i * 2 + 1];
}
void activate(int qp, ll val) {
activate(1, 1, n - 1, qp, val);
}
void update(int i, int l, int r, int ql, int qr, ll val) {
push(i, l, r);
if (l > qr || ql > r) return;
if (ql <= l && r <= qr) {
tree[i].lz = val;
push(i, l, r);
return;
}
int m = (l + r) / 2;
update(i * 2, l, m, ql, qr, val);
update(i * 2 + 1, m + 1, r, ql, qr, val);
tree[i] = tree[i * 2] + tree[i * 2 + 1];
}
void update(int ql, int qr, ll val) {
update(1, 1, n - 1, ql, qr, val);
}
Node query(int i, int l, int r, int ql, int qr) {
push(i, l, r);
if (ql <= l && r <= qr) {
return tree[i];
}
int m = (l + r) / 2;
Node res;
if (ql <= m) res = res + query(i * 2, l, m, ql, qr);
if (m + 1 <= qr) res = res + query(i * 2 + 1, m + 1, r, ql, qr);
return res;
}
ll query(int l, int r) {
if (l == r) return 0;
Node res = query(1, 1, n - 1, l, r - 1);
if (res.mnH < 0) return -1;
return res.sumD;
}
} seg;
int main() {
//~ ofstream cout("out.txt");
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n >> d;
seg.init(n);
vector<vector<array<int, 2>>> quer(n + 1);
vector<ll> a(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int l, r;
cin >> l >> r;
quer[r].push_back({l, i});
}
const ll INF = 4e18;
vector<pair<int, ll>> left = {{0, INF}};
vector<ll> res(q);
for (int i = 2; i <= n; ++i) {
//~ cerr << i << "\n";
seg.activate(i - 1, a[i - 1]);
//~ cerr << "activated at = " << i - 1 << "\n";
if (a[i] >= a[i - 1]) {
left.push_back({i - 1, (a[i] - a[i - 1]) / d});
} else {
ll need = (a[i - 1] - a[i] + d - 1) / d;
int r = i;
while (need > 0) {
auto& [l, have] = left.back();
ll take = min(need, have);
need -= take;
have -= take;
seg.update(l + 1, r - 1, take);
if (have == 0) {
r = l + 1;
left.pop_back();
}
}
}
for (auto [l, idx] : quer[i]) {
res[idx] = seg.query(l, i);
}
}
cerr << "Queries = \n";
for (auto& i : res) {
cout << i << "\n";
}
}
