#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
struct ST {
struct Node {
ll sum, Max;
Node operator+(const Node &other) {
return {sum + other.sum, max(Max, other.Max)};
}
};
int N;
vt<Node> st;
ST(const int n) : N(n), st(n<<1) {}
void update(int i, const Node v) {
st[i += N] = v;
while (i >>= 1)
st[i] = st[i<<1] + st[i<<1|1];
}
Node query(int l, int r) {
Node ret = {0, 0};
for (l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
if (l & 1)
ret = ret + st[l++];
if (r & 1)
ret = ret + st[--r];
}
return ret;
}
};
signed main() {
#ifndef DEBUG
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#endif
int N; ll D;
cin >> N >> D;
vt<ll> A(N+1), B(N+1), X(N+1), C(N+2);
vt<int> bad(N+1), psum2(N+1);
FOR(i, 1, N) {
cin >> A[i];
B[i] = A[i] % D;
X[i] = X[i-1] - B[i-1] + (B[i-1] > B[i]) * D + B[i];
C[i] = A[i] - X[i];
psum2[i] = psum2[i-1] + (B[i-1] > B[i]);
int lo = 0, hi = i-1;
while (lo < hi) {
const int mid = lo + hi + 1 >> 1;
if (D * (psum2[i] - psum2[mid]) + B[i] > A[i])
lo = mid;
else
hi = mid - 1;
}
bad[i] = lo;
#ifdef DEBUG
cout << i << ": " << C[i] << ' ' << X[i] << '\n';
#endif
}
vt<int> stk, parent(N+1);
vt<vt<int>> adj(N+2);
vt<ll> depth(N+2), psum(N+2);
ROF(i, N, 1) {
while (size(stk) && C[stk.back()] > C[i])
stk.pop_back();
parent[i] = size(stk) ? stk.back() : N + 1;
stk.push_back(i);
depth[i] = C[i] - C[parent[i]] + depth[parent[i]];
adj[parent[i]].push_back(i);
#ifdef DEBUG
cout << "parent " << i << ": " << parent[i] << ' ' << depth[i] << '\n';
#endif
}
FOR(i, 1, N)
psum[i] = psum[i-1] + depth[i];
int Q; cin >> Q;
vt<vt<ari2>> sweep(N+1);
FOR(i, 0, Q-1) {
int l, r;
cin >> l >> r;
sweep[r].push_back({l, i});
}
vt<ll> ans(Q);
set<int> roots;
ST st(N+1);
vt<int> szs(N+1);
FOR(i, 1, N) {
szs[i] = 1;
for (const auto &j : adj[i]) {
szs[i] += szs[j];
st.update(j, {0, bad[j]});
roots.erase(roots.find(j));
}
roots.insert(i);
st.update(i, {depth[i] * szs[i], bad[i]});
for (const auto &[j, qi] : sweep[i]) {
if (st.query(j, i).Max >= j)
ans[qi] = -1;
else {
const int y = *roots.lower_bound(j);
ans[qi] = psum[i] - psum[j-1] - st.query(y+1, i).sum - depth[y] * (y - j + 1);
ans[qi] /= D;
#ifdef DEBUG
cout << "yeet: " << psum[i] - psum[j-1] << ' ' << st.query(y+1, i).sum << ' ' << depth[y] << ' ' << (y - j + 1) << '\n';
#endif
}
}
}
for (const auto &i : ans)
cout << i << '\n';
}
