#include <bits/stdc++.h>
#define int long long
const int maxn = 3e5;
int N, D, Q;
int C[maxn + 5], L[maxn + 5], R[maxn + 5];
namespace SUB1 {
int d[4000], diff[4000], x[4000];
void solve() {
for (int i = 1; i < N; ++i) diff[i] = C[i] - C[i + 1];
for (int _ = 1; _ <= Q; ++_) {
int l = L[_], r = R[_], ans = 0;
for (int i = l; i <= r; ++i) {
d[i] = 0;
x[i] = 0;
}
for (int i = r - 1; i >= l; --i) {
if (d[i] < diff[i]) {
int cnt = (diff[i] - d[i] + D - 1) / D;
x[i] += cnt * D; x[i + 1] -= cnt * D;
ans += cnt;
d[i] += cnt * D;
d[i - 1] -= cnt * D;
}
x[i + 1] += d[i] - diff[i];
}
for (int i = l + 1; i <= r; ++i)
x[i] += x[i - 1];
bool ok = true;
for (int i = l; i <= r; ++i) {
ok &= (x[i] <= C[i]);
}
std::cout << (ok ? ans : -1) << '\n';
}
}
};
namespace SUB2 {
int pref[maxn + 5];
bool check_sub() {
bool ok = true;
for (int i = 1; i <= N; ++i)
ok &= (C[i] <= 1);
return ok;
}
void solve() {
for (int i = 1; i <= N; ++i)
pref[i] = pref[i - 1] + C[i];
for (int _ = 1; _ <= Q; ++_) {
int l = L[_], r = R[_];
int cnt = pref[r] - pref[l - 1];
int lb = l, rb = r, mn = r + 1;
while (lb <= rb) {
int mid = (lb + rb) >> 1;
if (pref[r] - pref[mid - 1] == r - mid + 1) {
mn = mid;
rb = mid - 1;
} else {
lb = mid + 1;
}
}
int ans = cnt - (r - mn + 1);
if (ans) {
std::cout << (D == 1 ? ans : -1) << '\n';
} else {
std::cout << 0 << '\n';
}
}
}
};
namespace SUB3 {
int id[maxn + 5], ans[maxn + 5], pref[maxn + 5];
struct segment_tree {
int info[4 * maxn + 5], tag[4 * maxn + 5];
void update(int id, int l, int r, int lb, int rb, int x) {
if (lb <= l && r <= rb) {
info[id] += (r - l + 1) * x;
tag[id] += x;
return;
}
int mid = (l + r) >> 1;
info[id << 1] += (mid - l + 1) * tag[id];
info[id << 1 | 1] += (r - mid) * tag[id];
tag[id << 1] += tag[id];
tag[id << 1 | 1] += tag[id];
tag[id] = 0;
if (lb <= mid)
update(id << 1, l, mid, lb, rb, x);
if (rb > mid)
update(id << 1 | 1, mid + 1, r, lb, rb, x);
info[id] = info[id << 1] + info[id << 1 | 1];
}
int get(int id, int l, int r, int lb, int rb) {
if (lb <= l && r <= rb)
return info[id];
int mid = (l + r) >> 1;
info[id << 1] += (mid - l + 1) * tag[id];
info[id << 1 | 1] += (r - mid) * tag[id];
tag[id << 1] += tag[id];
tag[id << 1 | 1] += tag[id];
tag[id] = 0;
int a = 0, b = 0;
if (lb <= mid)
a = get(id << 1, l, mid, lb, rb);
if (rb > mid)
b = get(id << 1 | 1, mid + 1, r, lb, rb);
return a + b;
}
void update(int l, int r, int x) {
update(1, 1, N, l, r, x);
}
int get(int l, int r) {
return get(1, 1, N, l, r);
}
} seg;
struct dta {
int val, l, r;
};
bool check_sub() {
return D == 1;
}
void solve() {
for (int i = 1; i <= Q; ++i) id[i] = i;
std::sort(id + 1, id + Q + 1, [&](int i, int j) {
return R[i] < R[j];
});
for (int i = 1; i <= N; ++i) pref[i] = pref[i - 1] + C[i];
std::vector<dta> vec;
for (int r = 1, ptr = 1; r <= N && ptr <= Q; ++r) {
while (!vec.empty() && vec.back().val >= C[r]) {
seg.update(vec.back().l, vec.back().r, -vec.back().val);
vec.pop_back();
}
if (vec.empty())
vec.push_back({C[r], 1, r});
else
vec.push_back({C[r], vec.back().r + 1, r});
seg.update(vec.back().l, vec.back().r, C[r]);
while (ptr <= Q && R[id[ptr]] == r) {
int num = id[ptr];
int lb = L[num], rb = R[num];
ans[num] = ((pref[rb] - pref[lb - 1]) - seg.get(lb, rb)) / D;
++ptr;
}
}
for (int i = 1; i <= Q; ++i)
std::cout << ans[i] << '\n';
}
};
namespace SUB4 {
int a[maxn + 5], pref[maxn + 5], sum[maxn + 5], p[maxn + 5];
bool check_sub() {
bool ok = true;
for (int i = 1; i < N; ++i)
ok &= (C[i] >= C[i + 1]);
return ok;
}
void solve() {
for (int i = 1; i <= N; ++i) p[i] = p[i - 1] + C[i];
for (int i = 2; i <= N; ++i) {
a[i] = ((C[i] - C[i - 1]) % D + D) % D;
pref[i] = pref[i - 1] + a[i];
sum[i] = sum[i - 1] + i * a[i];
}
std::function<int(int, int)> compute = [&](int l, int r) {
if (l > r) return 0ll;
int len = r - l + 1;
return (sum[r] - sum[l - 1]) - (pref[r] - pref[l - 1]) * (r - len);
};
for (int _ = 1; _ <= Q; ++_) {
int l = L[_], r = R[_];
if (C[r] < pref[r] - pref[l]) {
std::cout << -1 << '\n';
continue;
}
int len = r - l + 1;
std::cout << (p[r] - p[l - 1] - (C[r] * len - compute(l + 1, r))) / D << '\n';
}
}
};
signed main() {
// freopen("fish3.inp", "r", stdin);
std::cin.tie(0)->sync_with_stdio(0);
std::cin >> N >> D;
for (int i = 1; i <= N; ++i) std::cin >> C[i];
std::cin >> Q;
for (int i = 1; i <= Q; ++i) std::cin >> L[i] >> R[i];
if (SUB2::check_sub()) {
SUB2::solve();
return 0;
}
if (SUB3::check_sub()) {
SUB3::solve();
return 0;
}
if (SUB4::check_sub()) {
SUB4::solve();
return 0;
}
SUB1::solve();
return 0;
}
