#include <bits/stdc++.h>
using namespace std;
void print(int x, char sep = ' '){
cout << x << sep;
}
vector < int > solve(vector < int > &v, vector < int > &w, vector < pair < int, int > > &queries){
int n = v.size(), q = queries.size();
int mx[n][20] = {}, mx2[n][20], dp[n] = {};
vector < int > ans(q);
for(int i = 0; i < n; i++) mx[i][0] = min(i + v[i], n - 1);
for(int i = 0; i < n; i++) mx2[i][0] = min(i + w[i], n - 1);
for(int k = 1; k < 20; k++)
for(int i = 0; i + (1 << k) - 1 < n; i++)
mx[i][k] = max(mx[i][k - 1], mx[i + (1 << (k - 1))][k - 1]);
for(int k = 1; k < 20; k++)
for(int i = 0; i + (1 << k) - 1 < n; i++)
mx2[i][k] = max(mx2[i][k - 1], mx2[i + (1 << (k - 1))][k - 1]);
auto get = [&mx](int l, int r) {
int k = __lg(r - l + 1);
return max(mx[l][k], mx[r - (1 << k) + 1][k]);
};
auto get2 = [&mx2](int l, int r) {
int k = __lg(r - l + 1);
return max(mx2[l][k], mx2[r - (1 << k) + 1][k]);
};
for(int i = 0; i < q; i++){
auto [l, r] = queries[i];
if(l == r){
ans[i] = 0;
continue;
}
dp[0] = l;
for(int x = 1; x < n; x++){
dp[x] = get(l, dp[x - 1]);
if(x > 1) dp[x] = max(dp[x], get2(l, dp[x - 2]));
if(r <= dp[x]){
ans[i] = x;
break;
}
}
}
return ans;
}
