#include <bits/stdc++.h>
#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))
constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl
#define int long long
#define ld long double
#define pb push_back
#define rg ranges
using namespace std;
constexpr int inf = 1e18;
int n, D, q;
vector<int> a, b, c, ap, ans, minAp, pref;
vector<array<int, 3>> queries;
int tB;
vector<int> t, lz;
int cntL(int v) {
auto lv = 31 - __builtin_clz(v);
return tB / (1 << lv);
}
void tAdd(int l, int r, int x, int mL = 0, int mR = tB - 1, int v = 1) {
if(l > mR || r < mL) return;
if(l <= mL && mR <= r) {
lz[v] += x;
return;
}
auto md = (mL + mR) / 2 + 1;
tAdd(l, r, x, mL, md - 1, v * 2);
tAdd(l, r, x, md, mR, v * 2 + 1);
t[v] = t[v * 2] + t[v * 2 + 1] + (lz[v * 2] + lz[v * 2 + 1]) * cntL(v * 2);
}
int tSum(int l, int r, int mL = 0, int mR = tB - 1, int v = 1) {
if(l > mR || r < mL) return 0;
if(l <= mL && mR <= r) return t[v] + lz[v] * cntL(v);
auto md = (mL + mR) / 2 + 1;
int ans = 0;
ans += tSum(l, r, mL, md - 1, v * 2);
ans += tSum(l, r, md, mR, v * 2 + 1);
ans += lz[v] * (min(mR, r) - max(mL, l) + 1);
return ans;
}
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> D;
a.resize(n);
b.resize(n);
c.resize(n);
ap.resize(n);
pref.resize(n);
repIn(i, c) cin >> i;
cin >> q;
queries.resize(q);
ans.resize(q);
minAp.resize(q);
rep(i, 0, q) cin >> queries[i][0] >> queries[i][1], queries[i][2] = i;
tB = 1 << (32 - __builtin_clz(n - 1));
t.resize(2 * tB);
lz.resize(2 * tB);
rep(i, 0, n) a[i] = c[i] / D, b[i] = c[i] % D;
rg::sort(queries);
for(auto& [l, r, qi] : queries) l--, r--;
rep(i, 0, n) {
ap[i] = a[i];
rep(j, 1, i + 1) ap[i] -= (b[j] < b[j - 1]);
tAdd(i, i, ap[i]);
}
int lst = 0;
for(auto [l, r, qi] : queries) {
while(lst < l) {
lst++;
if(b[lst] < b[lst - 1]) tAdd(lst, n - 1, 1);
}
ans[qi] += tSum(l, r);
}
rep(i, 0, tB * 2) t[i] = lz[i] = 0;
set<pair<int, int>> sufMinS;
for(auto& [l, r, qi] : queries) swap(l, r);
rg::sort(queries);
for(auto& [l, r, qi] : queries) swap(l, r);
lst = -1;
sufMinS.insert({-1, -inf});
for(auto [l, r, qi] : queries) {
while(lst < r) {
lst++;
auto me = ap[lst];
auto st = lst;
auto pval = 0ll;
while(sufMinS.size() && sufMinS.rbegin() -> second > me) {
auto [i, val] = *sufMinS.rbegin();
tAdd(i + 1, st, -pval);
st = i;
pval = val;
sufMinS.erase({i, val});
}
if(sufMinS.size()) {
auto [i, val] = *sufMinS.rbegin();
tAdd(i + 1, st, -pval);
st = i + 1;
}
sufMinS.insert({lst, me});
tAdd(st, lst, me);
}
DEBUG {
int minSuf = inf;
vector<int> v;
repD(i, r, l - 1) {
minSuf = min(minSuf, ap[i]);
v.pb(minSuf);
}
rg::reverse(v);
repIn(i, v) DC << i << ' ';
DC << eol;
rep(i, l, r + 1) {
DC << tSum(i, i) << ' ';
assert(v[i - l] == tSum(i,i));
}
DC << eol;
DC << eol;
}
ans[qi] -= tSum(l, r);
minAp[qi] = tSum(l, l);
}
int sum = 0;
rep(i, 1, n) sum += b[i] < b[i - 1], pref[i] = sum;
for(auto [l, r, qi] : queries) {
sum = pref[l];
ans[qi] -= sum * (r - l + 1);
if(minAp[qi] + sum < 0) ans[qi] = -1;
}
repIn(i, ans) cout << i << '\n';
}
