#include "floppy.h"
#include <bits/stdc++.h>
#define ll int
#define ii pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define lwb lower_bound
#define upb upper_bound
#define ld double
#define ins insert
#define del erase
#define ull unsigned long long
using namespace std;
const ll big=4e4+9;
const ll inf=1e9;
const ll mod=1e9+7;
const ll hug=3e6;
struct tr{ll fi,se,th; tr(ll _fi=0, ll _se=0, ll _th=0){fi=_fi; se=_se; th=_th;}};
struct qu{ll fi,se,th,fo; qu(ll _fi=0, ll _se=0, ll _th=0, ll _fo=0){fi=_fi; se=_se; th=_th; fo=_fo;}};
ll mxz(ll &t, ll val){if (t<val){t=val; return 1;} return 0;}
ll mnz(ll &t, ll val){if (t>val){t=val; return 1;} return 0;}
ll qpw(ll n, ll k, ll m=mod){ll p=1, t=n%m; while (k){if (k&1) p=p*t%m; t=t*t%m; k>>=1;} return p;}
ll ran(){
ll s=0;
for (ll i=0; i<5; ++i) s^=(1ll*rand())<<(i*14ll);
return abs(s);
}
ll ran(ll l, ll r){
return ran()%(r-l+1)+l;
}
ll pmn[16][big];
ll a[big];
string s;
ll qmn(ll l, ll r){
ll t=log2(r-l+1);
ll L=pmn[t][l], R=pmn[t][r+1-(1ll<<t)];
return (a[L]>a[R]? L: R);
}
ll calc(ll l, ll r){
if (l==r){
s.pb('0'); s.pb('0');
return 0;
}
ll p=qmn(l,r);
if (l<=p-1) s.pb('1'); else s.pb('0');
if (p+1<=r) s.pb('1'); else s.pb('0');
if (l<=p-1) calc(l,p-1);
if (p+1<=r) calc(p+1,r);
return 0;
}
void read_array(ll iquifd, const vector<ll> &_a){
ll n=(ll)_a.size();
for (ll i=0; i<n; ++i) a[i]=_a[i];
for (ll i=0; i<n; ++i) pmn[0][i]=i;
for (ll j=1; (1ll<<j)<=n; ++j) for (ll i=0; i+(1ll<<j)-1<n; ++i){
ll L=pmn[j-1][i], R=pmn[j-1][i+(1ll<<(j-1))];
pmn[j][i]=(a[L]>a[R]? L: R);
}
s="";
calc(0,n-1);
// cout<<s<<"\n";
save_to_floppy(s);
return;
}
ll an=0;
ll tempo=0;
ll dfs(){
ll val=0;
char xl=s[2*tempo], xr=s[2*tempo+1];
if (xl=='1'){
++tempo;
mxz(val,dfs());
}
ll p=an; ++an;
if (xr=='1'){
++tempo;
mxz(val,dfs());
}
a[p]=val+1;
// cout<<p<<": "<<xl<<xr<<"\n";
return a[p];
}
vector<ll> solve_queries(ll qownhixe, ll n, const string &_s, const vector<ll> &x, const vector<ll> &y){
ll q=(ll)x.size();
vector<ll> ans(q);
s=_s;
dfs();
// for (ll i=0; i<n; ++i) cout<<a[i]<<" "; cout<<"\n";
for (ll i=0; i<n; ++i) pmn[0][i]=i;
for (ll j=1; (1ll<<j)<=n; ++j) for (ll i=0; i+(1ll<<j)-1<n; ++i){
ll L=pmn[j-1][i], R=pmn[j-1][i+(1ll<<(j-1))];
pmn[j][i]=(a[L]>a[R]? L: R);
}
for (ll i=0; i<q; ++i) ans[i]=qmn(x[i],y[i]);
// for (ll t: ans) cout<<t<<" "; cout<<"\n";
return ans;
}
//1 5 3 2 6 4
//111100010000
int mainn(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
freopen("INPUT.TXT","r",stdin);
// freopen("OUTPUT.TXT","w",stdout);
// ll tst=1;
// cin>>tst;
// for (; tst; --tst) solve();
read_array(1,{-10,500,30,20,60000,400});
solve_queries(1,6,"111100010000",{1,2,0,2},{4,5,1,3});
return 0;
}
