#include<bits/stdc++.h>
#include"highest.h"
using namespace std;
struct sparse_table{
private:
int N;
vector<int> val;
vector<vector<int>> mem;
public:
void init(vector<int> A){
N=(int)(A.size());
mem.assign(N,vector<int>(20));
val=A;
build();
}
void set(int p,int x){
val[p]=x;
}
void build(){
for(int i=0;i<N;i++){
mem[i][0]=val[i];
}
for(int j=1;j<20;j++){
for(int i=0;i<N;i++){
int k=i+(1<<(j-1));
if(k>=N) mem[i][j]=mem[i][j-1];
else mem[i][j]=max(mem[i][j-1],mem[k][j-1]);
}
}
}
int get(int p){
return val[p];
}
int prod(int l,int r){
if(l==r) return -1;
int length=r-l;
int h=bit_width((unsigned int)length)-1;
return max(mem[l][h],mem[r-(1<<h)][h]);
}
};
struct RMQ{
private:
int N;
const int B=20;
vector<int> val;
vector<int> pm_f;
vector<int> pm_b;
sparse_table st;
public:
void init(vector<int> A){
N=(int)(A.size());
val=A;
vector<int> st_init;
for(int i=0;i<N;i+=B){
int maximum=-1;
for(int j=i;j<i+B;j++) maximum=max(maximum,A[j]);
st_init.emplace_back(maximum);
}
st.init(st_init);
pm_f.resize(N);
pm_f[N-1]=A[N-1];
for(int i=N-2;i>=0;i--){
if((i+1)%B==0){
pm_f[i]=A[i];
}
else{
pm_f[i]=max(pm_f[i+1],A[i]);
}
}
pm_b.resize(N+1);
pm_b[0]=-1;
for(int i=1;i<=N;i++){
if((i-1)%B==0){
pm_b[i]=A[i-1];
}
else{
pm_b[i]=max(pm_b[i-1],A[i-1]);
}
}
}
int get(int p){
return val[p];
}
int prod(int l,int r){
if(l==r) return -1;
if(r/B-l/B<=1){
int res=-1;
for(int i=l;i<r;i++) res=max(res,val[i]);
return res;
}
int res=st.prod(l/B+1,r/B);
return max({res,pm_f[l],pm_b[r]});
}
};
vector<int> solve(vector<int> &v,vector<int> &w,vector<pair<int,int>> &queries){
int N=(int)(v.size());
vector<int> wsub(N);
for(int i=0;i<N;i++) wsub[i]=min(i+w[i],N-1);
RMQ seg_w;
seg_w.init(wsub);
vector<RMQ> dp1(20),dp2(20);
{
vector<int> dp1_init(N),dp2_init(N);
for(int i=0;i<N;i++){
dp1_init[i]=min(i+v[i],N-1);
dp2_init[i]=i;
}
dp1[0].init(dp1_init);
dp2[0].init(dp2_init);
}
for(int i=1;i<20;i++){
vector<int> dp1_init(N),dp2_init(N);
for(int j=0;j<N;j++){
{
int r=dp1[i-1].get(j);
int mem1=dp1[i-1].prod(j,r+1);
r=dp2[i-1].get(j);
r=seg_w.prod(j,r+1);
mem1=max(mem1,dp2[i-1].prod(j,r+1));
dp1_init[j]=mem1;
}
{
int r=dp1[i-1].get(j);
int mem2=dp2[i-1].prod(j,r+1);
r=dp2[i-1].get(j);
mem2=max(mem2,dp1[i-1].prod(j,r+1));
dp2_init[j]=mem2;
}
}
dp1[i].init(dp1_init);
dp2[i].init(dp2_init);
}
vector<int> ans;
for(auto[A,B] : queries){
int res=0,p0=A,p1=-1;
for(int bit=19;bit>=0;bit--){
int nres=(res|(1<<bit));
int mem0=dp1[bit].prod(A,p0+1);
if(p1!=-1){
int mem1=seg_w.prod(A,p1+1);
mem1=dp2[bit].prod(A,mem1+1);
mem0=max(mem0,mem1);
}
int mem1=dp2[bit].prod(A,p0+1);
if(p1!=-1){
int mem2=dp1[bit].prod(A,p1+1);
mem1=max(mem1,mem2);
}
if(mem0<B){
res=nres;
p0=mem0;
p1=mem1;
}
}
ans.emplace_back(res+1);
}
return ans;
}
