#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 300010, INF = 1e18;
struct mat {
int a[4][4];
mat() {
a[1][2] = a[1][3] = a[2][1] = a[2][3] = a[3][1] = a[3][2] = 0;
a[1][1] = a[2][2] = a[3][3] = 1;
}
mat operator*(const mat &m) const {
mat ans;
//// ans.a[1][1] = a[1][1] * m.a[1][1] + a[1][2] * m.a[2][1] + a[1][3] * m.a[3][1];
ans.a[1][1] = a[1][1] * m.a[1][1];
//// ans.a[1][2] = a[1][1] * m.a[1][2] + a[1][2] * m.a[2][2] + a[1][3] * m.a[3][2];
ans.a[1][2] = a[1][1] * m.a[1][2] + a[1][2];
//// ans.a[1][3] = a[1][1] * m.a[1][3] + a[1][2] * m.a[2][3] + a[1][3] * m.a[3][3];
//// ans.a[2][1] = a[2][1] * m.a[1][1] + a[2][2] * m.a[2][1] + a[2][3] * m.a[3][1];
//// ans.a[2][2] = a[2][1] * m.a[1][2] + a[2][2] * m.a[2][2] + a[2][3] * m.a[3][2];
//// ans.a[2][3] = a[2][1] * m.a[1][3] + a[2][2] * m.a[2][3] + a[2][3] * m.a[3][3];
ans.a[1][3] = 0ll;
ans.a[2][1] = 0ll;
ans.a[2][2] = 1ll;
ans.a[2][3] = 0ll;
ans.a[3][1] = a[3][1] * m.a[1][1] + a[3][3] * m.a[3][1];
ans.a[3][2] = a[3][1] * m.a[1][2] + a[3][2] + a[3][3] * m.a[3][2];
// ans.a[3][3] = a[3][2] * m.a[2][3] + a[3][3] * m.a[3][3];
ans.a[3][3] = 1ll;
return ans;
}
};
struct SegT {
mat t[N << 2];
bool vis[N << 2];
static inline int ls(int u) { return u << 1; }
static inline int rs(int u) { return u << 1 | 1; }
inline void pushdown(int u) {
if (vis[u]) {
t[ls(u)] = t[ls(u)] * t[u];
t[rs(u)] = t[rs(u)] * t[u];
t[u].a[1][2] = t[u].a[1][3] = t[u].a[2][1] = t[u].a[2][3] = t[u].a[3][1] = t[u].a[3][2] = 0;
t[u].a[1][1] = t[u].a[2][2] = t[u].a[3][3] = 1;
vis[u] = 0;
vis[ls(u)] = vis[rs(u)] = 1;
}
return;
}
void update(const int l, const int r, const int ql, const int qr, const int u, const mat &x) {
if (ql <= l && qr >= r) {
t[u] = t[u] * x;
vis[u] = 1;
// for (int i = 1; i <= 3; i++) {
// for (int j = 1; j <= 3; j++)cout << t[u].a[i][j] << " ";
// cout << '\n';
// }
return;
}
int mid((l + r) >> 1);
pushdown(u);
if (ql <= mid)update(l, mid, ql, qr, ls(u), x);
if (qr > mid)update(mid + 1, r, ql, qr, rs(u), x);
return;
}
int query(const int l, const int r, const int u, const int pos) {
// if (l == r) {
// for (int i = 1; i <= 3; i++) {
// for (int j = 1; j <= 3; j++)cout << t[u].a[i][j] << " ";
// cout << '\n';
// }
// return t[u];
// }
if (l == r) {
return u;
}
pushdown(u);
int mid((l + r) >> 1);
if (pos <= mid)return query(l, mid, ls(u), pos);
else return query(mid + 1, r, rs(u), pos);
}
};
SegT T;
int n, D, C[N], q, ans[N];
vector<pair<int, int>> qlist[N];
int check(int pos) {
mat nw;
nw = T.t[T.query(1, n, 1, pos)];
return INF * nw.a[1][1] + nw.a[3][1];
}
void work() {
for (int i = 1; i <= n; i++) {
int l(1), r(i), now(C[i] / D);
if (C[i] % D > C[i - 1] % D && i > 1) {
mat tmp;
tmp.a[3][1] = -1;
T.update(1, n, 1, i - 1, 1, tmp);
}
while (l < r) {
int mid((l + r) >> 1);
if (check(mid) >= now)r = mid;
else l = mid + 1;
}
if (l > 1) {
mat tmp;
tmp.a[1][2] = -1ll;
tmp.a[3][2] = now;
T.update(1, n, 1, l - 1, 1, tmp);
}
{
mat tmp;
tmp.a[1][1] = 0;
tmp.a[3][1] = now;
T.update(1, n, l, i, 1, tmp);
}
for (auto x: qlist[i]) {
mat tmp = T.t[T.query(1, n, 1, x.first)];
if (INF * tmp.a[1][1] + tmp.a[3][1] >= 0)
ans[x.second] = INF * tmp.a[1][2] + tmp.a[3][2];
else ans[x.second] = -1ll;
}
// for (int j = 1; j <= i; j++)
// cout << check(j) << ' ';
// cout << '\n';
}
return;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
// freopen("test.in", "r", stdin);
cin >> n >> D;
// cout<<clock()<<'\n';
for (int i = 1; i <= n; i++)cin >> C[n + 1 - i];
cin >> q;
for (int i = 1; i <= q; i++) {
int l, r;
cin >> l >> r;
swap(l, r);
l = n + 1 - l;
r = n + 1 - r;
qlist[r].push_back({l, i});
}
work();
// for (int k = 1; k <= 5; k++) {
// int now = T.query(1, n, 1, k);
// for (int i = 1; i <= 3; i++) {
// for (int j = 1; j <= 3; j++) {
// cout << T.t[now].a[i][j] << " ";
// }
// cout << '\n';
// }
// }
for (int i = 1; i <= q; i++)cout << ans[i] << '\n';
// cout<<clock()<<'\n';
return 0;
}
/*
* 6 3
16 14 13 8 6 5
4
1 4
2 5
3 3
1 6
*/
