#include<bits/stdc++.h>
#define ll long long
#define maxn 300005
using namespace std;
int n;
ll d;
ll a[maxn];
ll b[maxn];
ll sb[maxn];
ll dif[maxn];
ll sdif[maxn];
int lg[maxn];
ll rmq[maxn][20];
ll get_minB(int l,int r)
{
int k=__lg(r-l+1);
return min(rmq[l][k],rmq[r-(1<<k)+1][k]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>d;
lg[1]=0;
for(int i=2;i<=n;i++)
{
lg[i]=lg[i/2]+1;
}
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
dif[i]=((a[i+1]-a[i])%d+d)%d;
sdif[i]=sdif[i-1]+dif[i];
b[i]=rmq[i][0]=(a[i]-sdif[i-1]);
sb[i]=sb[i-1]+b[i];
}
for(int k=1;k<=lg[n]+1;k++)
{
for(int i=1;i+(1<<k)-1<=n;i++)
{
rmq[i][k]=min(rmq[i][k-1],rmq[i+(1<<(k-1))][k-1]);
}
}
int q;
cin>>q;
while(q--)
{
int l,r;
cin>>l>>r;
if(get_minB(l,r)<-(sdif[l-1]-a[l]%d))
{
cout<<-1<<'\n';
continue;
}
//cout<<'\n';
int pre=r;
ll ds=0;
for(int i=r-1;i>=l;i--)
{
if(b[i]>=b[pre])
{
}
else
{
ds+=-(pre-i)*b[pre];
pre=i;
}
}
ds+=(sb[r]-sb[l-1])-(pre-l+1)*b[pre];
cout<<ds/d<<'\n';
}
}
/*
s[i]=s[i-3]+(a[i-2]-s[i-3])%mod+(a[i-1]-a[i-2])%mod+(a[i]-a[i-1])%mod
s[i]=(a[l])%mod+(a[l+1]-a[l])%mod+...+(a[i]-a[i-1])%mod
(a[i]-sdif[i-1])+(sdif[l-1]-a[l]%d)
Voi mot thang r co dinh thi tat cac so chi cong
len mot luong co dinh
(a[i]-sdif[i-1])+(sdif[l-1]-a[l]%d)>=0
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |