#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define sp " "
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt","w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define LL node * 2
#define RR node * 2 + 1
#define mid (l + r) / 2
#define ll long long
#define MAXN 2000005
const int modulo = 1e9 + 7;
const ll INF = 2e18 +7;
pii mini[4 * MAXN], maks[4 * MAXN];
void push(int node, int l, int r){
if (l == r) return;
vector<array<int, 3>> v;
//cout<<"push : "<<l<<sp<<r<<sp<<maks[node].st<<sp<<mini[node].st<<endl;
v.pb({maks[node].nd, maks[node].st, 1});
v.pb({mini[node].nd, mini[node].st, 2});
sort(v.begin(), v.end());
vector<int> child = {LL, RR};
for (auto i : v){
int type = i[2], val = i[1], time = i[0];
// cout<<"!! "<<type<<sp<<val<<sp<<time<<endl;
for (auto gh : child){
if (type == 1){ // max
if (maks[gh].st <= val){
maks[gh] = {val, time};
if (mini[gh].st <= val)
mini[gh] = maks[gh];
}
}
else{
if (mini[gh].st >= val){
mini[gh] = {val, time};
if (maks[gh].st >= val){
maks[gh] = mini[gh];
}
}
}
//cout<<"pushed : "<<maks[gh].st<<sp<<mini[gh].st<<endl;
}
}
mini[node] = {modulo, 0};
maks[node] = {0, 0};
}
void build(int node, int l, int r){
maks[node] = {0, 0};
mini[node] = {modulo, 0};
if (l == r) return;
build(LL, l, mid);
build(RR, mid + 1, r);
}
void update(int node, int l, int r, int sl, int sr, int val, int time, int type){
push(node, l, r);
// cout<<l<<sp<<r<<endl;
if (l > sr || r < sl) return;
if (l >= sl && r <= sr){
if (type == 1){ //max operation
if (maks[node].st <= val){
maks[node] = {val, time};
if (mini[node].st <= val) mini[node] = maks[node];
}
}
else{
if (mini[node].st >= val){
mini[node] = {val, time};
if (maks[node].st >= val) maks[node] = mini[node];
}
}
return;
}
update(LL, l, mid, sl, sr, val, time, type);
update(RR, mid + 1, r, sl, sr, val, time, type);
}
int query(int node, int l, int r, int sl){
push(node, l, r);
if (l == r) {
return maks[node].st;
}
if (sl <= mid) return query(LL, l, mid, sl);
return query(RR, mid + 1, r, sl);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
build(1, 1, n);
for (int i = 0; i < k; i++){
left[i]++, right[i]++;
update(1, 1, n, left[i], right[i], height[i], i, op[i]);
}
for (int j = 1; j <= n; j++){
finalHeight[j - 1] = query(1, 1, n, j);
}
}
