Language: C++

//#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
//#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
//#pragma GCC target("avx2")  //Enable AVX
#include<bits/stdc++.h>
using namespace std;
#define int ll
#define all(a) begin(a),end(a)
#define F first
#define S second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int mod=1e9+7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int mul(int a,int b){
  return ((a)*1ll*(b))%mod;
}

void add(int &a,int b){
  a+=b;
  if(a>=mod)a-=mod;
}

int sub(int a,int b){
  a-=b;
  if(a<0){
    a+=mod;
  }
  return a;
}

int powz(int a,int b){
  int res=1;
  while(b){
    if(b&1){
      res=mul(res,a);
    }
    b/=2;
    a=mul(a,a);
  }
  return res;
}

template <typename A, typename B>
istream& operator>>(istream& input,pair<A,B>& x) {
  input>>x.F>>x.S;
  return input;
}

template <typename A>
istream& operator>>(istream& input,vector<A>& x) {
  for(auto& i:x)
    input>>i;
  return input;
}

template<typename A>
ostream& operator<<(ostream& output,vector<A>& x) {
  for(auto& i:x)
    output<<i<<' ';
  return output;
}

template<typename T>
vector<pair<T,int>> getvec(int n){
  vector<pair<T,int>>a(n);
  for(int i=0;i<a.size();i++){
    cin>>a[i].F;
    a[i].S=i;
  }
  return a;
}

void clr(auto &a,int n){
  a.clear();
  a.resize(n);
}

void unq(auto &a){
  sort(all(a));
  a.resize(unique(all(a))-a.begin());
}

const int N=100005;

int cycleNo[N];
vector<int>adj[N];
bool vis[N];
int nxt[N];
int n;

void dfs(int u,int p){
	if(vis[u]){
		return;
	}
	if(u==n-1){
		return;
	}
	vis[u]=true;
	cycleNo[u]=p;
	adj[p].pb(u);
	dfs(nxt[u],p);	
}

void solve(){
	cin>>n;
	vi a(n);
	cin>>a;
	int L;
	cin>>L;
	int q;
	cin>>q;
	vector<pair<int,int>>queries;
	for(int i=0;i<q;i++){
		int x,y;
		cin>>x>>y;
		x--;y--;
		queries.pb({x,y});
	}
	vector<int>ans(q,-1);
	vector<int>prf(n);
	for(int i=0;i<n-1;i++){
		prf[i+1]=a[i+1]-a[i];
		prf[i+1]+=prf[i];
	}
	for(int i=n-2;i>=0;i--){
		int l=i+1,r=n-1;
		int con=prf[i],val=i+1;
		while(l<=r){
			int mid=(l+r)/2;
			if((prf[mid]-con)<=L){
				l=mid+1;
				val=max(val,mid);
			}
			else{
				r=mid-1;
			}
		}
		nxt[i]=val;
	}
	for(int i=0;i<n-1;i++){
		if(vis[i]==false){
			dfs(i,i);
			sort(all(adj[i]));
		}
	}
	for(int i=0;i<q;i++){
		int x,y;
		tie(x,y)=queries[i];
		if(x<y){
			auto it=lower_bound(all(adj[cycleNo[x]]),y)-adj[cycleNo[x]].begin();
			auto it2=lower_bound(all(adj[cycleNo[x]]),x)-adj[cycleNo[x]].begin();
			ans[i]=it-it2;
		}
	}
	for(int i=0;i<n;i++){
		adj[i].clear();
		nxt[i]=0;
		vis[i]=false;
		prf[i]=0;
	}
	reverse(all(a));
	for(int i=0;i<n-1;i++){
		prf[i+1]=abs(a[i+1]-a[i]);
		prf[i+1]+=prf[i];
	}
	for(int i=n-2;i>=0;i--){
		int l=i+1,r=n-1;
		int con=prf[i],val=i+1;
		while(l<=r){
			int mid=(l+r)/2;
			if((prf[mid]-con)<=L){
				l=mid+1;
				val=max(val,mid);
			}
			else{
				r=mid-1;
			}
		}
		nxt[i]=val;
	}
	for(int i=0;i<n-1;i++){
		if(vis[i]==false){
			dfs(i,i);
			sort(all(adj[i]));
		}
	}
	for(int i=0;i<q;i++){
		int x,y;
		tie(x,y)=queries[i];
		x=n-x-1;
		y=n-y-1;
		if(x<y){
			auto it=lower_bound(all(adj[cycleNo[x]]),y)-adj[cycleNo[x]].begin();
			auto it2=lower_bound(all(adj[cycleNo[x]]),x)-adj[cycleNo[x]].begin();
			ans[i]=it-it2;
		}
	}
	for(auto i:ans){
		cout<<i<<'\n';
	}
}

signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tc=1;
  //cin>>tc;
  for(int _=0;_<tc;_++){
    //~cout<<"Case #"<<_+1<<": ";
    solve();
    if(_!=tc-1){
      cout<<'\n';
    }
  }
}

//#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
//#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
//#pragma GCC target("avx2")  //Enable AVX
#include<bits/stdc++.h>
using namespace std;
#define int ll
#define all(a) begin(a),end(a)
#define F first
#define S second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int mod=1e9+7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int mul(int a,int b){
  return ((a)*1ll*(b))%mod;
}

void add(int &a,int b){
  a+=b;
  if(a>=mod)a-=mod;
}

int sub(int a,int b){
  a-=b;
  if(a<0){
    a+=mod;
  }
  return a;
}

int powz(int a,int b){
  int res=1;
  while(b){
    if(b&1){
      res=mul(res,a);
    }
    b/=2;
    a=mul(a,a);
  }
  return res;
}

template <typename A, typename B>
istream& operator>>(istream& input,pair<A,B>& x) {
  input>>x.F>>x.S;
  return input;
}

template <typename A>
istream& operator>>(istream& input,vector<A>& x) {
  for(auto& i:x)
    input>>i;
  return input;
}

template<typename A>
ostream& operator<<(ostream& output,vector<A>& x) {
  for(auto& i:x)
    output<<i<<' ';
  return output;
}

template<typename T>
vector<pair<T,int>> getvec(int n){
  vector<pair<T,int>>a(n);
  for(int i=0;i<a.size();i++){
    cin>>a[i].F;
    a[i].S=i;
  }
  return a;
}

void clr(auto &a,int n){
  a.clear();
  a.resize(n);
}

void unq(auto &a){
  sort(all(a));
  a.resize(unique(all(a))-a.begin());
}

const int N=100005;

int cycleNo[N];
vector<int>adj[N];
bool vis[N];
int nxt[N];
int n;

void dfs(int u,int p){
	if(vis[u]){
		return;
	}
	if(u==n-1){
		return;
	}
	vis[u]=true;
	cycleNo[u]=p;
	adj[p].pb(u);
	dfs(nxt[u],p);	
}

void solve(){
	cin>>n;
	vi a(n);
	cin>>a;
	int L;
	cin>>L;
	int q;
	cin>>q;
	vector<pair<int,int>>queries;
	for(int i=0;i<q;i++){
		int x,y;
		cin>>x>>y;
		x--;y--;
		queries.pb({x,y});
	}
	vector<int>ans(q,-1);
	vector<int>prf(n);
	for(int i=0;i<n-1;i++){
		prf[i+1]=a[i+1]-a[i];
		prf[i+1]+=prf[i];
	}
	for(int i=n-2;i>=0;i--){
		int l=i+1,r=n-1;
		int con=prf[i],val=i+1;
		while(l<=r){
			int mid=(l+r)/2;
			if((prf[mid]-con)<=L){
				l=mid+1;
				val=max(val,mid);
			}
			else{
				r=mid-1;
			}
		}
		nxt[i]=val;
	}
	for(int i=0;i<n-1;i++){
		if(vis[i]==false){
			dfs(i,i);
			sort(all(adj[i]));
		}
	}
	for(int i=0;i<q;i++){
		int x,y;
		tie(x,y)=queries[i];
		if(x<y){
			auto it=lower_bound(all(adj[cycleNo[x]]),y)-adj[cycleNo[x]].begin();
			auto it2=lower_bound(all(adj[cycleNo[x]]),x)-adj[cycleNo[x]].begin();
			ans[i]=it-it2;
		}
	}
	for(int i=0;i<n;i++){
		adj[i].clear();
		nxt[i]=0;
		vis[i]=false;
		prf[i]=0;
	}
	reverse(all(a));
	for(int i=0;i<n-1;i++){
		prf[i+1]=abs(a[i+1]-a[i]);
		prf[i+1]+=prf[i];
	}
	for(int i=n-2;i>=0;i--){
		int l=i+1,r=n-1;
		int con=prf[i],val=i+1;
		while(l<=r){
			int mid=(l+r)/2;
			if((prf[mid]-con)<=L){
				l=mid+1;
				val=max(val,mid);
			}
			else{
				r=mid-1;
			}
		}
		nxt[i]=val;
	}
	for(int i=0;i<n-1;i++){
		if(vis[i]==false){
			dfs(i,i);
			sort(all(adj[i]));
		}
	}
	for(int i=0;i<q;i++){
		int x,y;
		tie(x,y)=queries[i];
		x=n-x-1;
		y=n-y-1;
		if(x<y){
			auto it=lower_bound(all(adj[cycleNo[x]]),y)-adj[cycleNo[x]].begin();
			auto it2=lower_bound(all(adj[cycleNo[x]]),x)-adj[cycleNo[x]].begin();
			ans[i]=it-it2;
		}
	}
	for(auto i:ans){
		cout<<i<<'\n';
	}
}

signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tc=1;
  //cin>>tc;
  for(int _=0;_<tc;_++){
    //~cout<<"Case #"<<_+1<<": ";
    solve();
    if(_!=tc-1){
      cout<<'\n';
    }
  }
}



Compiler output:
a.cc:85:10: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   85 | void clr(auto &a,int n){
      |          ^~~~
a.cc:90:10: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   90 | void unq(auto &a){
      |          ^~~~
a.cc:250:11: error: redefinition of 'const ll mod'
  250 | const int mod=1e9+7;
      |           ^~~
a.cc:22:11: note: 'const ll mod' previously defined here
   22 | const int mod=1e9+7;
      |           ^~~
a.cc:252:9: error: redefinition of 'std::mt19937 rng'
  252 | mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
      |         ^~~
a.cc:24:9: note: 'std::mt19937 rng' previously declared here
   24 | mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
      |         ^~~
a.cc:254:5: error: redefinition of 'll mul(ll, ll)'
  254 | int mul(int a,int b){
      |     ^~~
a.cc:26:5: note: 'll mul(ll, ll)' previously defined here
   26 | int mul(int a,int b){
      |     ^~~
a.cc:258:6: error: redefinition of 'void add(ll&, ll)'
  258 | void add(int &a,int b){
      |      ^~~
a.cc:30:6: note: 'void add(ll&, ll)' previously defined here
   30 | void add(int &a,int b){
      |      ^~~
a.cc:263:5: error: redefinition of 'll sub(ll, ll)'
  263 | int sub(int a,int b){
      |     ^~~
a.cc:35:5: note: 'll sub(ll, ll)' previously defined here
   35 | int sub(int a,int b){
      |     ^~~
a.cc:271:5: error: redefinition of 'll powz(ll, ll)'
  271 | int powz(int a,int b){
      |     ^~~~
a.cc:43:5: note: 'll powz(ll, ll)' previously defined here
   43 | int powz(int a,int b){
      |     ^~~~
a.cc:284:10: error: redefinition of 'template<class A, class B> std::istream& operator>>(std::istream&, std::pair<_T1, _T2>&)'
  284 | istream& operator>>(istream& input,pair<A,B>& x) {
      |          ^~~~~~~~
a.cc:56:10: note: 'template<class A, class B> std::istream& operator>>(std::istream&, std::pair<_T1, _T2>&)' previously declared here
   56 | istream& operator>>(istream& input,pair<A,B>& x) {
      |          ^~~~~~~~
a.cc:290:10: error: redefinition of 'template<class A> std::istream& operator>>(std::istream&, std::vector<_Tp>&)'
  290 | istream& operator>>(istream& input,vector<A>& x) {
      |          ^~~~~~~~
a.cc:62:10: note: 'template<class A> std::istream& operator>>(std::istream&, std::vector<_Tp>&)' previously declared here
   62 | istream& operator>>(istream& input,vector<A>& x) {
      |          ^~~~~~~~
a.cc:297:10: error: redefinition of 'template<class A> std::ostream& operator<<(std::ostream&, std::vector<_Tp>&)'
  297 | ostream& operator<<(ostream& output,vector<A>& x) {
      |          ^~~~~~~~
a.cc:69:10: note: 'template<class A> std::ostream& operator<<(std::ostream&, std::vector<_Tp>&)' previously declared here
   69 | ostream& operator<<(ostream& output,vector<A>& x) {
      |          ^~~~~~~~
a.cc:304:21: error: redefinition of 'template<class T> std::vector<std::pair<T, long long int> > getvec(ll)'
  304 | vector<pair<T,int>> getvec(int n){
      |                     ^~~~~~
a.cc:76:21: note: 'template<class T> std::vector<std::pair<T, long long int> > getvec(ll)' previously declared here
   76 | vector<pair<T,int>> getvec(int n){
      |                     ^~~~~~
a.cc:313:10: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  313 | void clr(auto &a,int n){
      |          ^~~~
a.cc:313:6: error: redefinition of 'template<class auto:30> void clr(auto:30&, ll)'
  313 | void clr(auto &a,int n){
      |      ^~~
a.cc:85:6: note: 'template<class auto:28> void clr(auto:28&, ll)' previously declared here
   85 | void clr(auto &a,int n){
      |      ^~~
a.cc:318:10: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  318 | void unq(auto &a){
      |          ^~~~
a.cc:318:6: error: redefinition of 'template<class auto:31> void unq(auto:31&)'
  318 | void unq(auto &a){
      |      ^~~
a.cc:90:6: note: 'template<class auto:29> void unq(auto:29&)' previously declared here
   90 | void unq(auto &a){
      |      ^~~
a.cc:323:11: error: redefinition of 'const ll N'
  323 | const int N=100005;
      |           ^
a.cc:95:11: note: 'const ll N' previously defined here
   95 | const int N=100005;
      |           ^
a.cc:325:5: error: redefinition of 'll cycleNo [100005]'
  325 | int cycleNo[N];
      |     ^~~~~~~
a.cc:97:5: note: 'll cycleNo [100005]' previously declared here
   97 | int cycleNo[N];
      |     ^~~~~~~
a.cc:326:12: error: redefinition of 'std::vector<long long int> adj [100005]'
  326 | vector<int>adj[N];
      |            ^~~
a.cc:98:12: note: 'std::vector<long long int> adj [100005]' previously declared here
   98 | vector<int>adj[N];
      |            ^~~
a.cc:327:6: error: redefinition of 'bool vis [100005]'
  327 | bool vis[N];
      |      ^~~
a.cc:99:6: note: 'bool vis [100005]' previously declared here
   99 | bool vis[N];
      |      ^~~
a.cc:328:5: error: redefinition of 'll nxt [100005]'
  328 | int nxt[N];
      |     ^~~
a.cc:100:5: note: 'll nxt [100005]' previously declared here
  100 | int nxt[N];
      |     ^~~
a.cc:329:5: error: redefinition of 'll n'
  329 | int n;
      |     ^
a.cc:101:5: note: 'll n' previously declared here
  101 | int n;
      |     ^
a.cc:331:6: error: redefinition of 'void dfs(ll, ll)'
  331 | void dfs(int u,int p){
      |      ^~~
a.cc:103:6: note: 'void dfs(ll, ll)' previously defined here
  103 | void dfs(int u,int p){
      |      ^~~
a.cc:344:6: error: redefinition of 'void solve()'
  344 | void solve(){
      |      ^~~~~
a.cc:116:6: note: 'void solve()' previously defined here
  116 | void solve(){
      |      ^~~~~
a.cc:443:8: error: redefinition of 'int main()'
  443 | signed main(){
      |        ^~~~
a.cc:215:8: note: 'int main()' previously defined here
  215 | signed main(){
      |        ^~~~