#include <bits/stdc++.h>
#include "wall.h"
#define pii pair<int,int>
#define F first
#define S second
#define mp make_pair
#define pb push_back
using namespace std;
const int mxn = 5e6 , N =5e5+100 ;
vector<vector<int>> sg(2,vector<int>(mxn,-1));
int query(int t ,int in,int l ,int r ,int ql ,int qr){
if(qr<l||r<ql) return -1 ;
if(ql<=l&&r<=qr) return sg[t][in] ;
int ans = query(t,in*2,l,(r+l)/2,ql,qr);
ans=max(ans,query(t,in*2+1,(r+l)/2+1,r,ql,qr)) ;
return ans;
}
int query(int i ,int t){
if(t) i=N-i;
return query(t,1,0,N,0,i);
}
void update(int t , int in, int l ,int r , int i,int v){
if(i<l||r<i) return ;
if(l==i&&r==i){
sg[t][in]=v ;
return ;
}
update(t,in*2,l,(r+l)/2,i,v);
update(t,in*2+1,(l+r)/2+1,r,i,v);
sg[t][in]=max(sg[t][in*2],sg[t][in*2+1]) ;
//return sg[t][in] ;
}
void update(int i , int v , int t){
if(t) i=N-i;
update(t,1,0,N,i,v) ;
return ;
}
void buildWall(int n,int k,int op[],int le[],int re[],int he[],int* ans){
vector<vector<array<int,3>>> in(n) , out(n);
set<int> ok ;
for(int i=0;i<k;i++){
if(op[i]==2) op[i]=0;
}
for(int i=0;i<k;i++) ok.insert(he[i]) ;
ok.insert(0);
int cnt =1;
map<int,int> ki ,rk ;
for(int x:ok) ki[x]=++cnt,rk[cnt]=x;
for(int i=0;i<k;i++){
in[le[i]].pb({op[i],ki[he[i]],i}) ;
out[re[i]].pb({op[i],ki[he[i]],i});
}
set<int> hey[2][cnt+1];
for(int i=0;i<n;i++){
for(auto x : in[i]){
int t = x[0] , he = x[1],tim=x[2] ;
hey[t][he].insert(tim) ;
tim = *(--hey[t][he].end()) ;
update(he,tim,t) ;
}
int l=1,r=cnt+1;
while(r-l!=1){
int md=(r+l)/2 ;
int val = query(md-1,0) ,vall = query(md,1) ;
if(vall>val) l=md ;
else r=md;
}
ans[i]=rk[l];
for(auto x: out[i]){
int t=x[0],he=x[1],tim=x[2];
hey[t][he].erase(tim) ;
update(he,-1,t);
if(hey[t][he].size()){
update(he,*(--hey[t][he].end()),t);
}
}
}
return ;
}
