#include <bits/stdc++.h>
using namespace std;
struct DuelSegmentTree {
int n;
vector<int>dat;
DuelSegmentTree(int N) {
n = 1;
while(n < N) {
n *= 2;
}
dat.resize(2*n,-1);
}
void update(int l,int r,int x) {
int now = l+n,le = l,ri = l+1;
while(true) {
if(now == 1) {
dat[1] = max(dat[1],x);
return;
}
int nle = 0,nri = 0;
if(1&now) {
nle = (le<<1)-ri;
nri = ri;
}
else {
nle = le;
nri = (ri<<1)-le;
}
if(l <= nle && nri <= r) {
now >>= 1;
continue;
}
le = nle;
ri = nri;
dat[now] = max(dat[now],x);
if(!(1&now)) {
return;
}
while(1&now) {
now >>= 1;
le = (le<<1)-ri;
ri = ri;
}
if(now == 0) return;
now++;
nle = ri;
nri = (ri<<1)-le;
if(l <= nle && nri <= r) {
le = nle;
ri = nri;
continue;
}
break;
}
now = r+n-1,le = r-1,ri = r;
while(true) {
if(now == 1) {
dat[1] = max(dat[1],x);
return;
}
int nle = 0,nri = 0;
if(1&now) {
nle = (le<<1)-ri;
nri = ri;
}
else {
nle = le;
nri = (ri<<1)-le;
}
if(l <= nle && nri <= r) {
now >>= 1;
continue;
}
dat[now] = max(dat[now],x);
if((1&now)) {
return;
}
le = nle;
ri = nri;
while(!(1&now)) {
now >>= 1;
le = le;
ri = (ri<<1)-le;
}
if(now == 0) return;
now--;
nri = le;
nle = (le<<1)-ri;
if(l <= nle && nri <= r) {
le = nle;
ri = nri;
continue;
}
break;
}
}
int query(int x) {
int ans = -1,now = x+n;
while(now > 0) {
ans = max(ans,dat[now]);
now >>= 1;
}
return ans;
}
};
void buildWall(int n, int k, int op[], int left[],int right[],int height[], int finalHeight[]) {
int MAX = 0;
for(int i = 0; i < k; i++) {
MAX = max(MAX,height[i]);
}
vector<int>l(n,0),r(n,MAX+1);
vector<array<int,3>>tmp1,tmp2;
for(int i = 0; i < k; i++) {
if(op[i] == 1) {
tmp1.push_back({height[i],1,i});
}
else {
tmp2.push_back({height[i],1,i});
}
}
while(true) {
bool f = false;
for(int i = 0; i < n; i++) {
if(l[i]+1 < r[i]) f = true;
}
if(!f) break;
vector<array<int,3>>q1 = tmp1,q2 = tmp2;
for(int i = 0; i < n; i++) {
if(l[i]+1 < r[i]) {
int mid = (l[i]+r[i])/2;
q1.push_back({mid,0,i});
q2.push_back({mid,0,i});
}
}
sort(q1.rbegin(),q1.rend());
sort(q2.begin(),q2.end());
vector<int>mx1(n),mx2(n);
DuelSegmentTree s1(n),s2(n);
{
for(int i = 0; i < q1.size(); i++) {
if(q1[i][1] == 1) {
int id = q1[i][2];
s1.update(left[id],right[id]+1,id);
}
else {
mx1[q1[i][2]] = s1.query(q1[i][2]);
}
}
}
{
for(int i = 0; i < q2.size(); i++) {
if(q2[i][1] == 1) {
int id = q2[i][2];
s2.update(left[id],right[id]+1,id);
}
else {
mx2[q2[i][2]] = s2.query(q2[i][2]);
}
}
}
for(int i = 0; i < n; i++) {
if(l[i]+1 < r[i]) {
int mid = (l[i]+r[i])/2;
if(mx2[i] < mx1[i]) {
l[i] = mid;
}
else {
r[i] = mid;
}
}
}
}
for(int i = 0; i < n; i++) {
finalHeight[i] = l[i];
}
}
