//#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 7;
const int MAX = 2000020;
int n, h[MAX], ans[MAX];
pair<int, int> st[MAX << 2];
void build(int id, int l, int r) {
st[id] = make_pair(-INF, INF);
if (l == r) {
st[id] = make_pair(h[l], h[l]);
return;
}
int mid = l + r >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
}
void update(int id, int l, int r) {
if (st[id].first > r) st[id] = make_pair(r, r); else
if (st[id].second < l) st[id] = make_pair(l, l); else
st[id] = make_pair(max(l, st[id].first), min(r, st[id].second));
}
void push(int id) {
update(id << 1, st[id].first, st[id].second);
update(id << 1 | 1, st[id].first, st[id].second); st[id] = make_pair(-INF, INF);
}
void update(int id, int l, int r, int u, int v, int t, int newH) {
if (l > v || r < u) return;
if (l >= u && r <= v) {
if (!t) update(id, newH, INF);
else update(id, -INF, newH);
return;
}
int mid = l + r >> 1; push(id);
update(id << 1, l, mid, u, v, t, newH);
update(id << 1 | 1, mid + 1, r, u, v, t, newH);
}
void magic(int id, int l, int r) {
if (l == r) {
ans[l] = st[id].first;
return;
}
int mid = l + r >> 1; push(id);
magic(id << 1, l, mid); magic(id << 1 | 1, mid + 1, r);
}
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++) {
update(1, 1, n, left[i] + 1, right[i] + 1, op[i] - 1, height[i]);
}
magic(1, 1, n);
for (int i = 0; i < n; ++i)
finalHeight[i] = ans[i + 1];
}
//int main(void) {
// n = 10;
// update(1, 1, n, 2, 9, 0, 4);
// update(1, 1, n, 5, 10, 1, 1);
// update(1, 1, n, 4, 7, 1, 5);
// update(1, 1, n, 1, 6, 0, 3);
// update(1, 1, n, 3, 3, 0, 5);
// update(1, 1, n, 7, 8, 1, 0);
// magic(1, 1, n);
// for (int i = 1; i <= n; ++i) {
// cout << ans[i] << ' ';
// }
//}
