#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6+4;
int n,k;
int tp[N],levo[N],desno[N],vis[N];
int drvo1[4*N],lazy1[4*N],drvo2[4*N],lazy2[4*N];
void push1(int i,int j,int node){
if(lazy1[node] != -1){
if(drvo1[node] < lazy1[node]) drvo1[node] = lazy1[node];
if(drvo2[node] < drvo1[node]) drvo2[node] = drvo1[node];
if(i != j){
lazy1[2*node] = lazy1[node];
lazy1[2*node+1] = lazy1[node];
}
lazy1[node] = -1;
}
}
void push2(int i,int j,int node){
if(lazy2[node] != -1){
if(drvo2[node] > lazy2[node]) drvo2[node] = lazy2[node];
if(drvo1[node] > drvo2[node]) drvo1[node] = drvo2[node];
if(i != j){
lazy2[2*node] = lazy2[node];
lazy2[2*node+1] = lazy2[node];
}
lazy2[node] = -1;
}
}
void update1(int i,int j,int l,int r,int val,int node){
push2(i,j,node); //l
push1(i,j,node);
if(j < l || i > r) return;
if(l <= i && r >= j){
lazy1[node] = val;
push1(i,j,node);
return;
}
int mid = i+(j-i)/2;
update1(i,mid,l,r,val,2*node);
update1(mid+1,j,l,r,val,2*node+1);
drvo1[node] = min(drvo1[2*node],drvo1[2*node+1]);
drvo2[node] = max(drvo2[2*node],drvo2[2*node+1]);
//drvo2[node] = max(drvo2[node],drvo1[node]);
}
void update2(int i,int j,int l,int r,int val,int node){
push1(i,j,node); //l
push2(i,j,node);
if(j < l || i > r) return;
if(l <= i && r >= j){
lazy2[node] = val;
push2(i,j,node);
return;
}
int mid = i+(j-i)/2;
update2(i,mid,l,r,val,2*node);
update2(mid+1,j,l,r,val,2*node+1);
drvo1[node] = min(drvo1[2*node],drvo1[2*node+1]);
drvo2[node] = max(drvo2[2*node],drvo2[2*node+1]);
//drvo1[node] = min(drvo1[node],drvo2[node]);
}
int daj(int i,int j,int l,int r,int node){
push1(i,j,node);
push2(i,j,node);
if(j < l || i > r) return 0;
if(l <= i && r >= j) return drvo2[node];
int mid = i+(j-i)/2;
return max(daj(i,mid,l,r,2*node),daj(mid+1,j,l,r,2*node+1));
}
void buildWall(int br1,int br2,int op[],int left[],int right[],int height[],int finalHeight[]){
n = br1;
k = br2;
for(int i = 0; i < k; i++){
tp[i+1] = op[i];
levo[i+1] = left[i]+1;
desno[i+1] = right[i]+1;
vis[i+1] = height[i];
}
for(int i = 0; i <= 4*n; i++) lazy1[i] = lazy2[i] = -1;
for(int i = 1; i <= k; i++){
if(tp[i] == 1){ /// dodavanje do vis[i], raste minimum
update1(1,n,levo[i],desno[i],vis[i],1);
}
else{ /// oduzimanje do vis[i], opada maksimum
update2(1,n,levo[i],desno[i],vis[i],1);
}
/*cout << "sad je ";
for(int i = 1; i <= n; i++){
cout << daj(1,n,i,i,1) << " ";
}
cout << endl;*/
for(int j = 1; j <= n; j++) daj(1,n,j,j,1);
}
for(int i = 1; i <= n; i++){
finalHeight[i-1] = daj(1,n,i,i,1);
}
}
