#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6+5;
const int INF = 1e9+7;
int n, arr[MAXN], st[4*MAXN], lz1[4*MAXN], lz2[4*MAXN];
void upd(int node, int a, int b, int mn, int mx, int l, int r)
{
if(l == a && r == b)
{
st[node] = max(st[node], mx);
st[node] = min(st[node], mn);
if(mx > lz1[node])
{
lz1[node] = lz2[node] = mx;
} else if(mn < lz2[node])
{
lz1[node] = lz2[node] = mn;
} else
{
lz1[node] = min(lz1[node], mn);
lz2[node] = max(lz2[node], mx);
}
}
int mid = (l+r)/2;
upd(2*node, l, mid, lz1[node], lz2[node], l, mid);
upd(2*node+1, mid+1, r, lz1[node], lz2[node], mid+1, r);
lz1[node] = INF;
lz2[node] = 0;
if(b <= mid)
{
upd(a, b, mn, mx, 2*node, l, mid);
} else if(a > mid)
{
upd(a, b, mn, mx, 2*node+1, mid+1, r);
} else
{
upd(a, mid, mn, mx, 2*node, l, mid);
upd(mid+1, b, mn, mx, 2*node+1, mid+1, r);
}
st[node] = min(st[2*node], st[2*node+1]);
}
void build(int node, int l, int r)
{
if(l == r)
{
lz1[node] = INF;
return;
}
int mid = (l+r)/2;
build(node*2, l, mid);
build(node*2+1, mid+1, r);
lz1[node] = INF;
}
void convert(int node, int l, int r)
{
if(l == r)
{
arr[l] = st[node];
}
int mid = (l+r)/2;
upd(2*node, l, mid, lz1[node], lz2[node], l, mid);
upd(2*node+1, mid+1, r, lz1[node], lz2[node], mid+1, r);
lz1[node] = INF;
lz2[node] = 0;
convert(2*node, l, mid);
convert(2*node+1, mid+1, r);
}
void buildWall(int _n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
n = _n;
build(1, 0, n-1);
// perform updates for each query.
for(int i = 0; i < k; i++)
{
if(op[i] == 1)
{
upd(1, left[i], right[i], INF, height[i], 0, n-1);
} else
{
upd(1, left[i], right[i], height[i], 0, 0, n-1);
}
}
}
