#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
#define MID ((l+r)/2)
struct node{
ll val;
node *L, *R;
void init(ll l, ll r){
val=INF;
if(l!=r){
L=new node;
L->init(l,MID);
R=new node;
R->init(MID+1,r);
}
}
void upd(ll l, ll r, ll i, ll x){
if(l==i && i==r){
val=x;
}
else if(l<=i && i<=r){
L->upd(l,MID,i,x);
R->upd(MID+1,r,i,x);
val=min(L->val,R->val);
}
}
ll ans(ll l, ll r, ll tl, ll tr){
if(tl<=l && r<=tr) return val;
else if(r<tl || tr<l) return INF;
else return min(L->ans(l,MID,tl,tr),R->ans(MID+1,r,tl,tr));
}
};
vector<int> solve(vector<int> &v, vector<int> &w, vector<pair<int,int>> &q){
ll n=v.size();
ll dist[n][n];
for(ll e=0; e<n; e++){
node seg;
seg.init(0,e);
dist[e][e]=0;
seg.upd(0,e,e,0);
for(ll i=e-1; i>=0; i--){
dist[i][e]=min(seg.ans(0,e,i+1,min(e,i+v[i]))+1,seg.ans(0,e,i+1,min(e,i+w[i]))+2);
seg.upd(0,e,i,dist[i][e]);
}
}
vector<int> ans;
for(auto i:q){
ans.push_back(dist[i.first][i.second]);
}
return ans;
}
