#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll N=2e6+5;
const ll MOD=1e9+7;
const ld pi=3.14159265359;
const ll INF=(1LL<<60);
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()
struct node{
ll l,r;
}seg[4*N];
node operator +(node A,node B){
if(A.l>=B.r){
return node{B.r,B.r};
}else if(A.r<=B.l){
return node{B.l,B.l};
}else{
assert(max(A.l,B.l)<=min(A.r,B.r));
return node{max(A.l,B.l),min(A.r,B.r)};
}
}
void ins(ll id,ll l,ll r,ll to,node del){
if(l==r-1){seg[id]=del;return ;}
ll mid=(l+r)>>1;
if(to<mid){
ins(id*2,l,mid,to,del);
}else{
ins(id*2+1,mid,r,to,del);
}
seg[id]=seg[id*2]+seg[id*2+1];
}
vector<ll> app[N],rem[N];
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
REP(i,k){
ins(1,0,k,i,node{0,INF});
app[left[i]].pb(i);
rem[right[i]].pb(i);
}
REP(i,n){
for(ll j:app[i]){
node tmp;
if(op[j]==1)tmp=node{height[j],INF};
else tmp=node{0,height[j]};
ins(1,0,k,j,tmp);
}
finalHeight[i]=seg[1].l;
for(ll j:rem[i]){
ins(1,0,k,j,node{0,INF});
}
}
//REP(i,n)cout<<finalHeight[i]<<" \n"[i==n-1];
}
/*
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int oper[]={1,2,2,1,1,2};
int l[] ={1,4,3,0,2,6};
int r[] ={8,9,6,5,2,7};
int h[] ={4,1,5,3,5,0};
int ans[10];
buildWall(10,6,oper,l,r,h,ans);
REP(i,10)cout<<ans[i]<<" \n"[i==9];
return 0;
}
//*/
