//#pragma target("arch=icelake-server")
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <cmath>
#include <random>
#include <chrono>
#include <iomanip>
#include <bitset>
using namespace std;
#define int long long
typedef long long ll;
typedef long double ld;
int log_ = 11;
int inf = 4000000007000000007;
long long mod = 1000000007;
int p = 499;
int NADIYA = 39;
struct segment_tree
{
vector <pair <int, int>> tree;
int size;
int size2;
void init(int n)
{
size2 = n;
size = 1;
while (size < n)
size *= 2;
tree.resize(size * 2, { 0 , 0 });
}
void build(int l, int r, int ind)
{
if (r - l == 1)
{
if (l < size2)
tree[ind].first = 0;
return;
}
int m = (r + l) / 2;
build(l, m, ind * 2 + 1);
build(m, r, ind * 2 + 2);
tree[ind].first = tree[ind * 2 + 1].first + tree[ind * 2 + 2].first;
}
void build(int n)
{
init(n);
//build(0, size, 0);
}
/*
void push(int ind)
{
if (tree[ind] != -1)
{
tree[ind * 2 + 1] = tree[ind];
tree[ind * 2 + 2] = tree[ind];
tree[ind] = -1;
}
}*/
void modified(int l, int r, int ind, int lx, int rx, int v)
{
if (r <= lx)
return;
if (rx <= l)
return;
if (r - l == 1)
{
tree[ind].second += v;
tree[ind].first += v * (r - l);
return;
}
if ((lx <= l) and (r <= rx))
{
tree[ind].second += v;
tree[ind].first += v * (r - l);
return;
}
int m = (r + l) / 2;
modified(l, m, ind * 2 + 1, lx, rx, v);
modified(m, r, ind * 2 + 2, lx, rx, v);
tree[ind].first = (tree[ind * 2 + 1].first + tree[ind * 2 + 2].first) + tree[ind].second * (r - l);
}
void modified(int lx, int rx, int v)
{
modified(0, size, 0, lx, rx, v);
}
int get(int l, int r, int ind, int lx, int rx, int sum)
{
if (r <= lx)
return 0;
if (rx <= l)
return 0;
if (r - l == 1)
{
return tree[ind].first + sum * (r - l);
}
if ((lx <= l) and (r <= rx))
{
return tree[ind].first + sum * (r - l);
}
sum += tree[ind].second;
int m = (r + l) / 2;
ll g1 = get(l, m, ind * 2 + 1, lx, rx, sum);
ll g2 = get(m, r, ind * 2 + 2, lx, rx, sum);
return g1 + g2;
}
int get(int l, int r)
{
return get(0, size, 0, l, r, 0);
}
};
vector <int> pref;
int get(int l, int r)
{
if (l == 0)
return pref[r];
else
return pref[r] - pref[l - 1];
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, d;
cin >> n >> d;
vector <int> a(n);
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
int p = 0;
pref.resize(n);
for (int i = 0; i < n; i++)
{
p += a[i];
pref[i] = p;
}
vector <vector <pair <int, int>>> q(n);
int q_;
cin >> q_;
vector <int> ans(q_);
for (int i = 0; i < q_; i++)
{
int l, r;
cin >> l >> r;
l--;
r--;
q[r].push_back({ l , i });
}
segment_tree st;
map <int , int> mp;
mp[0] = inf;
st.build(n);
st.modified(0, 1, a[0]);
for (int i = 1; i < n; i++)
{
st.modified(i, i + 1, a[i]);
if (a[i - 1] <= a[i])
{
int sz = (a[i] - a[i - 1]);
int c = (sz / d);
mp[i] = c;
}
else
{
int sz = (a[i - 1] - a[i]);
int c = (sz / d) + ((sz % d) > 0);
while (c > 0)
{
int ind = (*mp.rbegin()).first;
int x = mp[ind];
mp.erase(ind);
if (x <= c)
{
st.modified(ind, i , -d * x);
c -= x;
}
else
{
st.modified(ind, i , -d * c);
x -= c;
mp[ind] = x;
c = 0;
}
}
}
for (int j = 0; j < q[i].size(); j++)
{
int l = q[i][j].first;
int indx = q[i][j].second;
if (st.get(l, l + 1) < 0)
{
ans[indx] = -1;
continue;
}
ans[indx] = st.get(l, i + 1);
ans[indx] = (get(l, i) - ans[indx]) / d;
}
}
for (int i = 0; i < q_; i++)
{
cout << ans[i] << "\n";
}
}
/*5
1 2 1
2 3 1
2 4 1
1 5 4
*/
