#define F first
#define S second
#define rep(i,a,b) for(int i=a;!(a==b&&i!=b)&&((i<=b&&b>=a)||(i>=b&&a>=b));i+=(a<=b?1:-1))
#define pb push_back
#define Fbitl __builtin_ffs
#define bit1 __builtin_popcount
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
pair<int,int> seg[10000000] ;
int L , R , nn ;
bool segth[10000000] ;
int final[5000000] ;
struct act {
string type ;
int h ;
pair<int,int> range ;
};
int sth ( int idx , int l , int r , pair<int,int> mnx , int ans ){
if ( idx > (nn*2)+1 || segth[idx] ) return 0;
if ( l >= L && r <= R ) segth[idx] = true;
//cout << "hi " << idx << " " << ans << " " << endl;
if ( l > R || r < L ) return 0;
if ( mnx.F == ans ) {
if ( seg[idx].F >= mnx.F ) {
mnx = { seg[idx].F , 1000000 } ;
ans = seg[idx].F ;
}
else {
if ( mnx.F >= seg[idx].S ) {
mnx = { 0 , seg[idx].S } ;
ans = seg[idx].S ;
}
}
}
else if ( mnx.S == ans ) {
if ( seg[idx].S <= mnx.S ) {
mnx = { 0 , seg[idx].S } ;
ans = seg[idx].S ;
}
else {
if ( mnx.S <= seg[idx].F ) {
mnx = { seg[idx].F , 1000000 } ;
ans = seg[idx].F ;
}
}
}
if ( idx > nn ) {
//cout << ans << " " << idx-nn-1 << endl << endl;
final[idx-nn-1] = ans ;
return 0;
}
sth(idx*2,l,(l+r)/2,mnx,ans);
sth(idx*2+1,(l+r)/2+1,r,mnx,ans);
return 0;
}
int segment(int idx , int l , int r , pair<int,int> mnx ){
if ( idx > (nn*2+1) || segth[idx] ) return 0;
if ( l > R || r < L ) return 0;
pair <int,int> best ;
best = {max(mnx.F,seg[idx].F),min(mnx.S,seg[idx].S)} ;
if ( best == seg[idx] ) return 0;
if (mnx.F >= seg[idx].S ) {
if ( l == r ) {
final[idx-nn-1] = seg[idx].S ;
segth[idx] = true;
}
sth(idx*2,l,(l+r)/2,{0,seg[idx].S},seg[idx].S);
sth(idx*2+1,(l+r)/2+1,r,{0,seg[idx].S},seg[idx].S);
}
else if ( mnx.S <= seg[idx].F ) {
if ( l == r ) {
final[idx-nn-1] = seg[idx].F ;
segth[idx] = true;
}
sth(idx*2,l,(l+r)/2,{seg[idx].F,1000000},seg[idx].F);
sth(idx*2+1,(l+r)/2+1,r,{seg[idx].F,1000000},seg[idx].F);
}
if (!(l >= L && r <= R)) {
segment(idx*2 ,l,(l+r)/2,best);
segment(idx*2+1,(l+r)/2+1,r,best);
} else seg[idx] = best ;
return 0;
}
void buildWall(int n, int k, int op[], int left[] , int right[],int height[], int finalHeight[]){
queue <act> q ;
act a ;
for ( int i = k-1 ; i >= 0 ; i-- ) {
a.type = (op[i]==1?"min":"max") ;
a.h = height[i] ;
a.range = {left[i],right[i]} ;
q.push(a);
}
a.type = "max" ;
a.h = 0 ;
nn = log2(n);
if (pow(2,nn) != n) nn++;
nn = pow(2,nn)-1 ;
a.range = {0,nn} ;
q.push(a);
for ( int i = (nn*2)+1 ; i >= 1 ; i-- ) seg[i] = {0,1000000} ;
while ( !q.empty() ) {
L = q.front().range.F ;
R = q.front().range.S ;
pair<int,int> b ;
if ( q.front().type == "min" ) b = {q.front().h,1000000} ;
else b = {0,q.front().h} ;
segment(1,0,nn,b);
q.pop();
}
for ( int i = 0 ; i < n ; i++ ) {
finalHeight[i] = final[i] ;
//cout << final[i] << " " ;
}
}
/*int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n , k ;
vi op , l , r , h , f ;
op = { 1 , 2 , 1 , 2 } ;
l = {0,0,0,0} ;
r = {0,0,1,1} ;
h = {3,4,1,5} ;
f = {0,0,0,0} ;
n = 2 ;
k = 4 ;
buildWall(n,k,op,l,r,h,f);
return 0;
}*/
