#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6+5;
const int mxval = 1e5;
struct phase{
int ty, h, id;
phase(int _ty, int _h, int _id): ty(_ty), h(_h), id(_id){};
};
vector<phase> vec[maxn];
set<int> mx[mxval + 5][2];
int st[4*mxval + 20][2];
void edit(int ty, int pos, int l = 0, int r = mxval, int id = 1){
if(l == r)st[id][ty] = (mx[l][ty].empty() ? 0 : *mx[l][ty].rbegin());
else {
int mid = (l+r)>>1;
if(pos <= mid)edit(ty, pos, l, mid, id<<1);
else edit(ty, pos, mid+1, r, id<<1|1);
st[id][ty] = max(st[id<<1][ty], st[id<<1|1][ty]);
}
}
int query(int lmax = 1, int rmax = 0, int l = 0, int r = mxval, int id = 1){
if(l == r)return l;
else {
int mid = (l+r)>>1;
if(max(st[id<<1][1], lmax) > max(st[id<<1|1][0], rmax))return query(lmax, max(st[id<<1|1][0], rmax), l, mid, id<<1);
else return query(max(st[id<<1][1], lmax), rmax, mid+1, r, id<<1|1);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i = 0; i < k; i++){
vec[left[i]].push_back(phase(op[i]-1, height[i], i+2));
vec[right[i] + 1].push_back(phase(op[i]-1, height[i], i+2));
}
for(int i = 0; i < n; i++){
for(auto v: vec[i]){
if(mx[v.h][v.ty].find(v.id) != mx[v.h][v.ty].end())mx[v.h][v.ty].erase(v.id);
else mx[v.h][v.ty].insert(v.id);
edit(v.ty, v.h);
}
finalHeight[i] = query();
}
}
