// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())
using ll = long long;
template<class T> using V = vector<T>;
template<class T, size_t SZ> using AR = array<T, SZ>;
using vi = V<int>;
using vl = V<ll>;
const int nax = (1 << 19);
const ll INF = 1e13 + 1008;
ll SUM[2 * nax], MN[2 * nax], lzy[2 * nax];
void pull(int x) {
SUM[x] = SUM[2 * x] + SUM[2 * x + 1];
MN[x] = min(MN[2 * x], MN[2 * x + 1]);
}
void push(int x, int L, int R) {
if (lzy[x] != INF) {
SUM[x] = lzy[x] * 1LL * (R - L + 1);
MN[x] = lzy[x];
if (L != R) for(int i = 0; i < 2; i++) lzy[2 * x + i] = lzy[x];
}
lzy[x] = INF;
}
void upd(int l, int r, ll v, int x = 1, int L = 0, int R = nax - 1) {
push(x, L, R); if (r < L || R < l) return;
if (l <= L && R <= r) {
lzy[x] = v; push(x, L, R); return;
}
int M = (L + R) / 2;
upd(l, r, v, 2 * x, L, M);
upd(l, r, v, 2 * x + 1, M + 1, R);
pull(x);
}
ll sum(int l, int r, int x = 1, int L = 0, int R = nax - 1) {
push(x, L, R); if (r < L || R < l) return 0LL;
if (l <= L && R <= r) return SUM[x];
int M = (L + R) / 2;
return sum(l, r, 2 * x, L, M) + sum(l, r, 2 * x + 1, M + 1, R);
}
ll mn(int l, int r, int x = 1, int L = 0, int R = nax - 1) {
push(x, L, R); if (r < L || R < l) return INF;
if (l <= L && R <= r) return MN[x];
int M = (L + R) / 2;
return min(mn(l, r, 2 * x, L, M), mn(l, r, 2 * x + 1, M + 1, R));
}
int main() {
cin.tie(0)->sync_with_stdio(0);
for(int i = 0; i < 2 * nax; i++) {
SUM[i] = 0;
MN[i] = 0;
lzy[i] = INF;
}
int N; ll K; cin >> N >> K;
vl C(N); for(auto& x : C) cin >> x;
int Q; cin >> Q;
V<V<AR<int, 2>>> QRY(N);
for(int i = 0; i < Q; i++) {
int l, r; cin >> l >> r; --l, --r;
QRY[r].pb({l, i});
}
vi R(N, 0);
vl D(N), A(N);
for(int i = 0; i < N; i++) {
D[i] = C[i] / K;
C[i] %= K;
if (i) {
R[i] = R[i - 1];
if (C[i] < C[i - 1]) R[i]++;
}
A[i] = D[i] - R[i];
// cout << i << " -> " << A[i] << " " << C[i] << " " << D[i] << " " << R[i] << endl;
}
vl P = {0};
for(auto& x : A) P.pb(P.back() + x);
auto qry = [&](int l, int r) { return P[r + 1] - P[l]; };
vi stk = {-1}; vl ans(Q, -1);
for(int r = 0; r < N; r++) {
while(stk.back() != -1 && A[stk.back()] > A[r]) stk.pop_back();
// cout << stk.back() + 1 << " " << r << " " << A[r] << endl;
upd(stk.back() + 1, r, A[r]);
stk.pb(r);
for(auto& [l, i] : QRY[r]) {
// ll S = qry(l, r);
// ll s = sum(l, r);
// cout << l << " " << r << " " << i << " ---> " << S << " " << s << endl;
// cout << mn(l, r) << " <-> " << R[l] << endl;
ans[i] = max(ans[i], qry(l, r) - sum(l, r));
}
}
for(auto& x : ans) cout << x << nl;
exit(0-0);
}
