#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
void up(pair<int, int>& a, int b) {
a.first = max(a.first, b);
if (a.first > a.second) a.second = a.first;
}
void down(pair<int, int>& a, int b) {
a.second = min(a.second, b);
if (a.first > a.second) a.first = a.second;
}
struct segtree {
int n, sz;
vector<pair<int, int>> range;
segtree(int sz) : sz(sz) {
n = 1;
while (n < sz) n *= 2;
range.resize(2 * n - 1);
}
void prop(int node, int l, int r) {
if (r != l + 1) {
if (range[node].first != INT32_MIN) {
up(range[node * 2 + 1], range[node].first);
up(range[node * 2 + 2], range[node].first);
}
if (range[node].second != INT32_MAX) {
down(range[node * 2 + 1], range[node].second);
down(range[node * 2 + 2], range[node].second);
}
range[node] = {INT32_MIN, INT32_MAX};
}
}
void upd(int node, int l, int r, int a, int b, int h, bool u) {
prop(node, l, r);
if (r <= a || l >= b) return;
if (a <= l && r <= b) {
if (u) up(range[node], h);
else down(range[node], h);
return;
}
int m = (l + r) / 2;
upd(node * 2 + 1, l, m, a, b, h, u);
upd(node * 2 + 2, m, r, a, b, h, u);
}
void upd(int a, int b, int h, bool u) {
upd(0, 0, n, a, b + 1, h, u);
}
void get(int node, int l, int r, int v[]) {
prop(node, l, r);
if (r == l + 1) {
if (l < sz) v[l] = range[node].first;
return;
}
int m = (l + r) / 2;
get(node * 2 + 1, l, m, v);
get(node * 2 + 2, m, r, v);
}
void get(int v[]) {
get(0, 0, n, v);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
segtree st(n);
for (int i = 0; i < k; ++i) {
st.upd(left[i], right[i], height[i], (op[i] == 1));
}
st.get(finalHeight);
}
/*int main() {
int finalHeight[7];
int op[] = {1, 1, 2, 1, 2};
int left[] = {2, 4, 3, 1, 0};
int right[] = {4, 5, 4, 2, 3};
int height[] = {4, 5, 4, 1, 3};
buildWall(7, 5, op, left, right, height, finalHeight);
for (int i : finalHeight) {
cout << i << ' ';
}
cout << '\n';
}*/
