#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ull unsigned long long
#define lll __int128_t
#define ulll __uint128_t
#define ld long double
#define lld __float128
#define fi first
#define se second
#define mp make_pair
#define fast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
template<typename T>
using V = vector<T>;
template<typename T>
using VV = V<V<T>>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U>
bool chmax(T &x, U v) {return (v > x)? x=v,1 : 0;}
template<typename T, typename U>
bool chmin(T &x, U v) {return (v < x)? x=v,1 : 0;}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd64(chrono::steady_clock::now().time_since_epoch().count());
extern const int MOD;
struct mod
{
int val;
mod() : val(0) {}
mod(ll val) : val(((val % MOD) + MOD) % MOD) {} // fuck c++ modulos
mod operator+(const mod& a) const { return mod((val + a.val) % MOD); }
mod operator-(const mod& a) const { return mod((val + MOD - a.val) % MOD); }
mod operator-() const { return mod((MOD-val) % MOD);}
mod operator*(const mod& a) const { return mod(((ll)val * a.val) % MOD); }
template<typename T>
mod operator^(T power) const {
mod res = 1, a = val;
for(; power; power >>= 1, a = a*a) if(power & 1) res = res*a;
return res;
}
mod operator~() const { return *this ^ (MOD-2); }
mod operator/(const mod& a) const { return *this * (~a); }
friend istream& operator>>(istream& s, mod& x) { return s >> x.val, s; }
friend ostream& operator<<(ostream& s, const mod& x) { return s << x.val, s; }
operator int() const { return val; }
};
namespace fact
{
mod *f, *nf;
void precalc(int n) {
f = new mod[n+1], nf = new mod[n+1];
int i;
for(i = 1, f[0] = 1; i <= n; i++) f[i] = f[i-1]*mod(i);
for(i = n-1, nf[n] = ~f[n]; i >= 0; i--) nf[i] = nf[i+1]*mod(i+1);
}
mod fact(int n) { return f[n]; }
mod n_fact(int n) { return nf[n]; }
mod c(int n, int k) { return fact(n) * n_fact(k) * n_fact(n-k); }
};
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #define DEBUG
#ifdef DEBUG
#define _dark "\e[34m"
#define _bright "\e[38;5;220m"
#define _reset "\e[39m\n"
template<typename T, typename = void>
struct is_iterable : std::false_type {};
template<typename T>
struct is_iterable<T, std::void_t<
decltype(std::begin(std::declval<T>())),
decltype(std::end(std::declval<T>()))
>> : std::true_type {};
template<typename T>
inline enable_if_t<!is_iterable<T>::value, void>
__print(const T &x) { cerr << _bright << x; }
template<typename T, typename U>
inline void __print(const pair<T,U> &x) {
cerr << _dark << "(";
__print(x.fi);
cerr << _dark << ", ";
__print(x.se);
cerr << _dark << ")";
}
template<typename T>
inline void _print_iterable(T begin, T end, bool lines=false);
template<typename T>
inline void _print_set(const T &x) {
cerr << _dark << "{";
_print_iterable(x.begin(), x.end());
cerr << _dark << "}";
}
template<typename T>
inline void _print_list(const T &x) {
cerr << _dark << "[";
_print_iterable(x.begin(), x.end());
cerr << _dark << "]";
}
template<typename T>
inline void _print_map(const T &x);
template<typename T>
inline enable_if_t<is_iterable<T>::value, void> __print(const T &x) { _print_set(x); }
template<typename T>
inline void __print(const vector<T> &x) { _print_list(x); }
template<typename T, typename U>
inline void __print(const map<T, U> &x) { _print_map(x); }
template<typename T, typename U>
inline void __print(const unordered_map<T, U> &x) { _print_map(x); }
template<typename T, typename U>
inline void __print(const gp_hash_table<T, U> &x) { _print_map(x); }
template<typename T, typename U>
inline void __print(const cc_hash_table<T, U> &x) { _print_map(x); }
inline void _print() {}
template<typename T>
inline void _print(const T &x, auto... y) {
__print(x);
if(sizeof...(y)) cerr << _dark << ", ";
_print(y...);
}
template<typename T>
inline void _print_iterable(T begin, T end, bool lines) {
bool p = 0;
for(T it = begin; it != end; it++) {
if(p) cerr << _dark << "," << (lines ? "\n" : " ");
__print(*it);
p = 1;
}
}
template<typename T>
inline void _print_map(const T &x) {
cerr << _dark << "{";
bool p = 0;
for(const auto &i : x) {
if(p) cerr << _dark << ", ";
__print(i.fi);
cerr << _dark << "->";
__print(i.se);
p = 1;
}
cerr << _dark << "}";
}
template<typename T>
inline void _print_2d(T begin, T end, int size) {
bool p = 0;
for(T it = begin; it != end; it++) {
if(p) cerr << "\n";
_print_iterable(*it, *it+size);
p = 1;
}
}
#define _source source_location::current()
#define debug_pref(name, a...) cerr << _dark << _source.file_name() << ":" << _source.line() << ":" << _source.column() << " " << name << "(" << _bright << #a << _dark << ")";
#define debug(a...) {debug_pref("debug", a); cerr << _dark << " = "; _print(a); cerr << _reset;}
#define debug_1d(begin, end) {debug_pref("debug_1d", begin, end); cerr << _dark << " = ["; _print_iterable(begin, end, false); cerr << _dark << "]" << _reset;}
#define debug_lines(begin, end) {debug_pref("debug_lines", begin, end); cerr << _dark << " = [\n"; _print_iterable(begin, end, true); cerr << _dark << "\n]" << _reset;}
#define debug_2d(begin, n, m) {debug_pref("debug_2d", begin, end); cerr << _dark << " = [\n"; _print_2d(begin, begin+n, m); cerr << _dark << "\n]" << _reset;}
#endif
#ifndef DEBUG
#define debug(a...)
#define debug_1d(begin, end)
#define debug_lines(begin, end)
#define debug_2d(begin, n, m)
#endif
#define mtst int T; cin >> T; for(int test = 0; test < T; test++)
const int MOD = 1e9+7;
/*
the only issue is that jumps change dynamically. Only when we add element i
can we update max= on range [i+1, i+v[i]]
What does this mean for our stack?
Its a prefix of our stack and all updated values become obsolete except for the last one?
for the meantime yes, but they might become useful in the future.
What value can become good suddenly? Its the last one on the segment
So we just remove all values from the stack that have v[j] <= x and we add v[i] itself
*/
const int MAXN = 500005;
const int MLOG = 19;
int nxt[MAXN][MLOG];
vector<int> qr[MAXN];
vector<int> st;
inline void add(int i, vector<int> &v)
{
int nx = -1;
{
int lc = 0, rc = st.size();
while(lc != rc)
{
int m = (lc + rc) / 2;
if(st[m] > v[i])
lc = m+1;
else
rc = m;
}
nx = lc == st.size() ? -1 : st[lc];
}
nxt[i][0] = nx;
for(int j = 1; j < MLOG; j++)
{
if(nxt[i][j-1] == -1)
nxt[i][j] = -1;
else
nxt[i][j] = nxt[nxt[i][j-1]][j-1];
}
st.push_back(i);
}
vector<int> solve(vector<int> &v, vector<int> &w, vector<pair<int,int>> &queries)
{
int n = v.size();
for(int i = 0; i < n; i++)
{
v[i] = min(n-1, i+v[i]);
w[i] = min(n-1, i+w[i]);
}
int q = queries.size();
vector<int> ans(q);
for(int i = 0; i < q; i++)
{
qr[queries[i].fi].push_back(i);
}
for(int r = n-1; r >= 0; r--)
{
while(!st.empty() && st.back() <= v[r] && v[st.back()] < w[r])
{
st.pop_back();
}
if(v[r] > r && (st.empty() || st.back() > v[r]))
{
v[v[r]] = w[r];
add(v[r], v);
}
debug_1d(st.begin(), st.end());
add(r, v);
for(int i : qr[r])
{
ans[i] = 0;
int v = r;
int dst = queries[i].se;
for(int j = MLOG-1; j >= 0; j--)
{
int nx = nxt[v][j];
if(nx == -1 || nx >= dst)
continue;
v = nx;
ans[i] += (1 << j);
}
if(dst != r)
ans[i]++;
}
}
return ans;
}
/*
*/
