#include <bits/stdc++.h>
#define forint(i, N) for (int i = 0; i < (N); i++)
using namespace std;
vector<int> mintree(10000000, 0);
vector<int> maxtree(10000000, 0);
void updatemin(int node, int a, int b, int x, int y, int k) {
if (a <= x && y <= b) {
if (mintree[node] >= k) return;
mintree[node] = k;
if (maxtree[node] < mintree[node]) {
maxtree[node] = k;
}
if (mintree[node * 2 + 1] < mintree[node]) {
mintree[node * 2 + 1] = mintree[node];
if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) {
maxtree[node * 2 + 1] = mintree[node * 2 + 1];
}
}
if (mintree[node * 2 + 2] < mintree[node]){
mintree[node * 2 + 2] = mintree[node];
if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) {
maxtree[node * 2 + 2] = mintree[node * 2 + 2];
}
}
return;
}
if (mintree[node * 2 + 1] < mintree[node]) {
mintree[node * 2 + 1] = mintree[node];
if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) {
maxtree[node * 2 + 1] = mintree[node * 2 + 1];
}
}
if (mintree[node * 2 + 2] < mintree[node]){
mintree[node * 2 + 2] = mintree[node];
if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) {
maxtree[node * 2 + 2] = mintree[node * 2 + 2];
}
}
if (maxtree[node * 2 + 1] > maxtree[node]) {
maxtree[node * 2 + 1] = maxtree[node];
if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) {
mintree[node * 2 + 1] = maxtree[node * 2 + 1];
}
}
if (maxtree[node * 2 + 2] > maxtree[node]) {
maxtree[node * 2 + 2] = maxtree[node];
if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) {
mintree[node * 2 + 2] = maxtree[node * 2 + 2];
}
}
if ((x + y) / 2 >= a) {
updatemin(node * 2 + 1, a, b, x, (x + y) / 2, k);
}
if ((x + y) / 2 + 1 <= b) {
updatemin(node * 2 + 2, a, b, (x + y) / 2 + 1, y, k);
}
maxtree[node] = max(maxtree[node * 2 + 1], maxtree[node * 2 + 2]);
mintree[node] = min(mintree[node * 2 + 1], mintree[node * 2 + 2]);
if (maxtree[node] < mintree[node]) {
maxtree[node] = mintree[node];
}
}
void updatemax(int node, int a, int b, int x, int y, int k) {
if (a <= x && y <= b) {
if (maxtree[node] <= k) return;
maxtree[node] = k;
if (maxtree[node] < mintree[node]) {
mintree[node] = k;
}
if (maxtree[node * 2 + 1] > maxtree[node]) {
maxtree[node * 2 + 1] = maxtree[node];
if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) {
mintree[node * 2 + 1] = maxtree[node * 2 + 1];
}
}
if (maxtree[node * 2 + 2] > maxtree[node]) {
maxtree[node * 2 + 2] = maxtree[node];
if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) {
mintree[node * 2 + 2] = maxtree[node * 2 + 2];
}
}
return;
}
if (maxtree[node * 2 + 1] > maxtree[node]) {
maxtree[node * 2 + 1] = maxtree[node];
if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) {
mintree[node * 2 + 1] = maxtree[node * 2 + 1];
}
}
if (maxtree[node * 2 + 2] > maxtree[node]) {
maxtree[node * 2 + 2] = maxtree[node];
if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) {
mintree[node * 2 + 2] = maxtree[node * 2 + 2];
}
}
if (mintree[node * 2 + 1] < mintree[node]) {
mintree[node * 2 + 1] = mintree[node];
if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) {
maxtree[node * 2 + 1] = mintree[node * 2 + 1];
}
}
if (mintree[node * 2 + 2] < mintree[node]){
mintree[node * 2 + 2] = mintree[node];
if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) {
maxtree[node * 2 + 2] = mintree[node * 2 + 2];
}
}
if ((x + y) / 2 >= a) {
updatemax(node * 2 + 1, a, b, x, (x + y) / 2, k);
}
if ((x + y) / 2 + 1 <= b) {
updatemax(node * 2 + 2, a, b, (x + y) / 2 + 1, y, k);
}
maxtree[node] = max(maxtree[node * 2 + 1], maxtree[node * 2 + 2]);
mintree[node] = min(mintree[node * 2 + 1], mintree[node * 2 + 2]);
if (maxtree[node] < mintree[node]) {
mintree[node] = maxtree[node];
}
}
int pos = 0;
vector<int> heightfinal;
void search(int node, int x, int y, int target) {
//cerr << target << " ---- " << mintree[node] << " ---- " << maxtree[node] << " - - " << x << "--" << y << endl;
if (mintree[node] == maxtree[node]) {
for (int i = target; i <= y; i++) {
heightfinal[i] = mintree[node];
}
pos = y + 1;
return;
}
if (mintree[node * 2 + 1] < mintree[node]) {
mintree[node * 2 + 1] = mintree[node];
if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) maxtree[node * 2 + 1] = mintree[node * 2 + 1];
}
if (mintree[node * 2 + 2] < mintree[node]) {
mintree[node * 2 + 2] = mintree[node];
if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) maxtree[node * 2 + 2] = mintree[node * 2 + 2];
}
if (maxtree[node * 2 + 1] > maxtree[node]) {
maxtree[node * 2 + 1] = maxtree[node];
if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) mintree[node * 2 + 1] = maxtree[node * 2 + 1];
}
if (maxtree[node * 2 + 2] > maxtree[node]) {
maxtree[node * 2 + 2] = maxtree[node];
if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) mintree[node * 2 + 2] = maxtree[node * 2 + 2];
}
if ((x + y) / 2 >= target) {
search(node * 2 + 1, x, (x + y) / 2, target);
}
else {
search(node * 2 + 2, (x + y) / 2 + 1, y, target);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
forint(i, k) {
if (op[i] == 1) {
updatemin(0, left[i], right[i], 0, n - 1, height[i]);
}
else {
updatemax(0, left[i], right[i], 0, n - 1, height[i]);
}
}
forint(i, 12) {
cerr << mintree[i] << " - " << maxtree[i] << endl;
}
heightfinal.resize(n);
while (pos < n) {
//cerr << "hello" << endl;
search(0, 0, n - 1, pos);
}
forint(i, n) {
finalHeight[i] = heightfinal[i];
}
}
