#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pp pair<ll, ll>
#define vp vector<pp>
#define inf 1000000000
#define mod 1000000007
struct SegTree{
vi Itree;
void init(ll n){
Itree.clear();
while(n & (n - 1)) n++;
Itree.resize(2*n, -inf);
}
void update(ll ind, ll val){
ind += Itree.size() / 2;
Itree[ind] = val;
while(ind > 1){
ind /= 2;
Itree[ind] = max(Itree[2*ind], Itree[2*ind + 1]);
}
}
/*ll get2(ll u, ll l, ll r, ll a, ll b){
if(l == a && r == b){
return Itree[u];
}
ll s = (a + b) / 2;
if(r <= s) return get2(2*u, l, r, a, s);
else if(l >= s) return get2(2*u + 1, l, r, s, b);
else return max(get2(2*u, l, s, a, s), get2(2*u + 1, s, r, s, b));
}*/
ll get2(ll u, ll l, ll r, ll a, ll b){
ll res = -inf;
for (l += Itree.size()/2, r += Itree.size()/2; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
res = max(res, Itree[l]);
l++;
}
if (r & 1) {
r--;
res = max(res, Itree[r]);
}
}
return res;
}
ll get(ll l, ll r){
if(r > Itree.size() / 2) return inf;
if(r == l + 1){
return Itree[l + Itree.size()/ 2];
}
return get2(1, l, r, 0, Itree.size() / 2);
}
};
ll calc(ll y){
ll mins = 0;
if((y % 2) == 0) mins = 1;
return (1 << ((y / 2) + 1)) - mins;
}
vector<int> solve(vector<int> &A, vector<int> &B, vector<pair<int,int>> &queries){
ll n = A.size();
ll q = queries.size();
ll k = log2(n) + 2;
k *= 2;
vector<SegTree> dp(k);
for(int i = 0; i < k; i++){
dp[i].init(n);
}
for(int i = 0; i < n; i++){
dp[0].update(i, i + A[i]);
}
for(int i = 0; i < n; i++){
ll x = dp[0].get(i, min((ll)i + A[i] + 1, n));
if(x > i + B[i]){
B[i] = x - i;
}
dp[1].update(i, i + B[i]);
}
for(int i = 2; i < dp.size(); i += 2){
for(int j = 0; j < n; j++){
ll kam = dp[i - 2].get(j, j + 1);
ll ans = dp[i - 1].get(j, kam + 1);
ll kam2 = dp[i - 1].get(j, j + 1);
ll ans2 = dp[i - 2].get(j, kam2 + 1);
dp[i].update(j, max(ans, ans2));
ll ans3 = dp[i - 1].get(j, kam2 + 1);
ll kam4 = dp[1].get(j, kam + 1);
ll ans4 = dp[i - 2].get(j, kam4 + 1);
dp[i + 1].update(j, max(ans3, ans4));
}
}
vector<int> ans(q, 0);
for(int ind = 0; ind < q; ind++){
ll l = queries[ind].first;
ll r = queries[ind].second;
if(l == r) continue;
ll prev = 0;
bool done = false;
for(int i = dp.size() - 2; i >= 0; i -= 2){
ll kam = dp[i].get(l, l + 1);
ll kam2 = dp[i + 1].get(l, l + 1);
if(kam2 >= r && kam < r){
ans[ind] = calc(i + 1);
done = true;
break;
}
if(kam < r){
prev = i;
break;
}
}
if(done) continue;
pp akt = {dp[prev].get(l, l + 1), dp[prev + 1].get(l, l + 1)};
ans[ind] += calc(prev);
if(akt.first >= r){
continue;
}else if(akt.second >= r){
ans[ind]++;
continue;
}
for(int i = prev - 2; i >= 0; i -= 2){
ll ans1 = dp[i + 1].get(l, akt.first + 1);
ll ans2 = dp[i].get(l, akt.second + 1);
ll ans3 = dp[i + 1].get(l, akt.second + 1);
ll kam4 = dp[1].get(l, akt.first + 1);
ll ans4 = dp[i].get(l, kam4 + 1);
ll ANS = max(ans1, ans2);
ll ANS2 = max(ans3, ans4);
if(ANS >= r) continue;
ans[ind] += calc(i + 1);
if(ANS2 >= r){
ans[ind]++;
done = true;
break;
}
akt = {ANS, ANS2};
}
if(done) continue;
if(akt.first >= r){
continue;
}else if(akt.second >= r){
ans[ind]++;
continue;
}
ll i = 0;
ll ans1 = dp[i + 1].get(l, akt.first + 1);
ll ans2 = dp[i].get(l, akt.second + 1);
ll ans3 = dp[i + 1].get(l, akt.second + 1);
ll kam4 = dp[1].get(l, akt.first + 1);
ll ans4 = dp[i].get(l, kam4 + 1);
ll ANS = max(ans1, ans2);
ll ANS2 = max(ans3, ans4);
if(ANS >= r) ans[ind] += 2;
else if(ANS2 >= r) ans[ind] += 3;
}
return ans;
}
