#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#include "wall.h"
const int N=2e6+99;
int n,m,q,mx0,mx1;
int ans[N],seg[2][N];
vector<pair<int,int>> A;
vector<pair<int,pair<int,int>>> vec[N];
void upd(int x,int val,int s,int id=1,int l=0,int r=m){
if(r<=x || x<l) return ;
if(l+1==r){
seg[s][id]=val;
return ;
}
int mid=(l+r)>>1;
upd(x,val,s,id<<1,l,mid);
upd(x,val,s,id<<1|1,mid,r);
seg[s][id]=max(seg[s][id<<1],seg[s][id<<1|1]);
}
int get(int id=1,int l=0,int r=m){
if(l+1==r) return A[l].F;
int mid=(l+r)>>1;
if(max(mx0,seg[0][id<<1])>=max(mx1,seg[1][id<<1|1])){
maxm(mx1,seg[1][id<<1|1]);
return get(id<<1,l,mid);
}
maxm(mx0,seg[0][id<<1]);
return get(id<<1|1,mid,r);
}
void buildWall(int _n,int _k,int op[],int left[],int right[],int height[],int finalHeight[]){
n=_n;
q=_k;
f(i,0,q) A.pb({height[i],i}),right[i]++,op[i]=2-op[i];
A.pb({0,-1});
sort(all(A));
f(i,0,q){
int x=lower_bound(all(A),mp(height[i],i))-A.begin();
vec[left[i]].pb({op[i],{x,i+1}});
vec[right[i]].pb({op[i],{x,0}});
}
m=A.size();
f(i,0,n){
for(auto p : vec[i]) upd(p.S.F,p.S.S,p.F);
mx0=mx1=0;
ans[i]=get();
}
f(i,0,n) finalHeight[i]=ans[i];
}
