#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include <D:/debug.h> #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif #define fi first #define se second #define pii pair<int,int> #define pll pair<long long,long long> #define int long long const int N = 3e5 + 5, mod = 1e9 + 7, imod = (mod + 1) / 2; const long long inf = 1e18; int n, a[N], d,q; int seg[4*N],lazy[4*N]; void down(int crr,int l,int r){ if(lazy[crr]){ const int x=lazy[crr],mid=l+r>>1; lazy[crr]=0; lazy[crr*2]+=x; lazy[crr*2+1]+=x; seg[crr*2]+=x*(mid-l+1); seg[crr*2+1]+=x*(r-mid); } } void upd(int crr,int l,int r,int lm,int rm,int val){ if(l>rm || lm>r) return; if(lm<=l && r<=rm){ seg[crr]+=val*(r-l+1); lazy[crr]+=val; return; } down(crr,l,r); int mid=(l+r)>>1; upd(crr*2,l,mid,lm,rm,val); upd(crr*2+1,mid+1,r,lm,rm,val); seg[crr]=seg[crr*2]+seg[crr*2+1]; } int get(int crr,int l,int r,int lm,int rm){ if(l>rm || lm>r) return 0; if(lm<=l && r<=rm) return seg[crr]; down(crr,l,r); int mid=(l+r)>>1; return get(crr*2,l,mid,lm,rm)+get(crr*2+1,mid+1,r,lm,rm); } int ans[N]; vector<pii> event[N]; int solve(int u){ return a[u]-get(1,1,n,u,u)*d; } signed main(){ //freopen("GAME.inp","r",stdin); //freopen("MESSAGE.out","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> d; for(int i=1;i<=n;i++) cin >> a[i]; cin>>q; for(int i=1;i<=q;i++){ int l,r; cin>>l>>r; event[r].push_back({l,i}); } vector<int> st; for(int i=1;i<=n;i++){ int r=i; while(!st.empty()){ int l=st.back(); int x=solve(r-1),y=solve(r); if(x<=y) break; upd(1,1,n,l,r-1,(x-y+d-1)/d); r=l; st.pop_back(); } st.push_back(r); for(const pii j:event[i]){ if(solve(j.fi)<0) ans[j.se]=-1; else ans[j.se]=get(1,1,n,j.fi,i); } } for(int i=1;i<=q;i++){ cout<<ans[i]<<"\n"; } }