#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
typedef pair<ll, ll> pll;
#define vc vector
#define st first
#define nd second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define pub push_back
#define pob pop_back
const ll INF = 1e18;
ll minl(ll a, ll b) {
if (a <= b)
return a;
return b;
}
namespace Tree {
ll base;
vc<ll> tsum, tmin, lazy;
void init(ll n) {
base = 1;
while (base < n)
base *= 2;
tsum.assign(2 * base, 0);
tmin.assign(2 * base, INF);
lazy.assign(2 * base, INF);
}
void push(ll i, ll li, ll ri, ll s) {
if (lazy[i] == INF)
return;
tmin[li] = tmin[ri] = lazy[i];
tsum[li] = tsum[ri] = s * lazy[i];
lazy[li] = lazy[ri] = lazy[i];
lazy[i] = INF;
}
void update(ll ql, ll qr, ll qx, ll i = 1, ll l = 0, ll r = base - 1) {
if (qr < l or r < ql)
return;
ll s = r - l + 1;
if (ql <= l and r <= qr) {
tmin[i] = qx;
tsum[i] = qx * s;
lazy[i] = qx;
return;
}
ll m = (l + r) / 2;
ll li = 2 * i;
ll ri = li + 1;
push(i, li, ri, s / 2);
update(ql, qr, qx, li, l, m);
update(ql, qr, qx, ri, m + 1, r);
tsum[i] = tsum[li] + tsum[ri];
tmin[i] = minl(tmin[li], tmin[ri]);
}
ll quesum(ll ql, ll qr, ll i = 1, ll l = 0, ll r = base - 1) {
if (qr < l or r < ql)
return 0;
if (ql <= l and r <= qr)
return tsum[i];
ll m = (l + r) / 2;
ll li = 2 * i;
ll ri = li + 1;
ll s = r - l + 1;
push(i, li, ri, s / 2);
return quesum(ql, qr, li, l, m) + quesum(ql, qr, ri, m + 1, r);
}
ll quemin(ll ql, ll qr, ll i = 1, ll l = 0, ll r = base - 1) {
if (qr < l or r < ql)
return INF;
if (ql <= l and r <= qr)
return tmin[i];
ll m = (l + r) / 2;
ll li = 2 * i;
ll ri = li + 1;
ll s = r - l + 1;
push(i, li, ri, s / 2);
return minl(quemin(ql, qr, li, l, m), quemin(ql, qr, ri, m + 1, r));
}
};
struct Qu {
ll l, r;
};
ll n, D, q;
vc<ll> a;
vc<Qu> qus;
vc<ll> p, b, pb, res;
vc<vc<Qu>> cnt;
vc<pll> stk;
ll mod(ll x) {
x %= D;
if (x < 0)
x += D;
return x;
}
void input() {
int tmp;
cin >> tmp;
n = tmp;
cin >> tmp;
D = tmp;
a.resize(n + 1);
a[0] = 0;
for (ll i = 1; i <= n; i++) {
cin >> tmp;
a[i] = tmp;
}
cin >> tmp;
q = tmp;
qus.resize(q);
for (auto &qu : qus) {
cin >> tmp;
qu.l = tmp;
cin >> tmp;
qu.r = tmp;
}
}
void preprocess() {
p.resize(n + 1);
p[0] = 0;
for (ll i = 1; i <= n; i++)
p[i] = p[i - 1] + mod(a[i] - a[i - 1]);
b.resize(n + 1);
pb.resize(n + 1);
b[0] = pb[0] = 0;
for (ll i = 1; i <= n; i++) {
b[i] = a[i] - p[i];
pb[i] = pb[i - 1] + b[i];
}
Tree::init(n);
}
void update(ll i) {
while (not stk.empty() and stk.back().st >= b[i])
stk.pob();
ll l;
if (stk.empty())
l = 1;
else
l = stk.back().nd + 1;
Tree::update(l, i, b[i]);
stk.pub({b[i], i});
}
ll query(ll l, ll r) {
if (Tree::quemin(l, r) < -p[l])
return -1;
ll ret = pb[r] - pb[l - 1];
ret -= Tree::quesum(l, r);
return ret / D;
}
void sweep() {
cnt.assign(n + 1, vc<Qu>());
for (ll i = 0; i < q; i++)
cnt[qus[i].r].pub({qus[i].l, i});
res.resize(q);
for (ll i = 1; i <= n; i++) {
update(i);
for (auto &[l, id] : cnt[i])
res[id] = query(l, i);
}
}
void output() {
for (ll i = 0; i < q; i++)
cout << (long long)res[i] << "\n";
}
void program() {
input();
preprocess();
sweep();
output();
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
program();
return 0;
}
