#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = int;
const int MAXN = 2000001; // 1-based
int N;
ll A[MAXN];
struct Node {
ll sum; // Sum tag
ll max1; // Max value
ll max2; // Second Max value
ll maxc; // Max value count
ll min1; // Min value
ll min2; // Second Min value
ll minc; // Min value count
} T[MAXN * 4];
void merge(int t) {
// sum
T[t].sum = T[t << 1].sum + T[t << 1 | 1].sum;
// max
if (T[t << 1].max1 == T[t << 1 | 1].max1) {
T[t].max1 = T[t << 1].max1;
T[t].max2 = max(T[t << 1].max2, T[t << 1 | 1].max2);
T[t].maxc = T[t << 1].maxc + T[t << 1 | 1].maxc;
} else {
if (T[t << 1].max1 > T[t << 1 | 1].max1) {
T[t].max1 = T[t << 1].max1;
T[t].max2 = max(T[t << 1].max2, T[t << 1 | 1].max1);
T[t].maxc = T[t << 1].maxc;
} else {
T[t].max1 = T[t << 1 | 1].max1;
T[t].max2 = max(T[t << 1].max1, T[t << 1 | 1].max2);
T[t].maxc = T[t << 1 | 1].maxc;
}
}
// min
if (T[t << 1].min1 == T[t << 1 | 1].min1) {
T[t].min1 = T[t << 1].min1;
T[t].min2 = min(T[t << 1].min2, T[t << 1 | 1].min2);
T[t].minc = T[t << 1].minc + T[t << 1 | 1].minc;
} else {
if (T[t << 1].min1 < T[t << 1 | 1].min1) {
T[t].min1 = T[t << 1].min1;
T[t].min2 = min(T[t << 1].min2, T[t << 1 | 1].min1);
T[t].minc = T[t << 1].minc;
} else {
T[t].min1 = T[t << 1 | 1].min1;
T[t].min2 = min(T[t << 1].min1, T[t << 1 | 1].min2);
T[t].minc = T[t << 1 | 1].minc;
}
}
}
// corresponds to a chmin update
void push_max(int t, ll v, bool l) {
if (v >= T[t].max1) { return; }
T[t].sum -= T[t].max1 * T[t].maxc;
T[t].max1 = v;
T[t].sum += T[t].max1 * T[t].maxc;
if (l) {
T[t].min1 = T[t].max1;
} else {
if (v <= T[t].min1) {
T[t].min1 = v;
} else if (v < T[t].min2) {
T[t].min2 = v;
}
}
}
// corresponds to a chmax update
void push_min(int t, ll v, bool l) {
if (v <= T[t].min1) { return; }
T[t].sum -= T[t].min1 * T[t].minc;
T[t].min1 = v;
T[t].sum += T[t].min1 * T[t].minc;
if (l) {
T[t].max1 = T[t].min1;
} else {
if (v >= T[t].max1) {
T[t].max1 = v;
} else if (v > T[t].max2) {
T[t].max2 = v;
}
}
}
void pushdown(int t, int tl, int tr) {
if (tl == tr) return;
// sum
int tm = (tl + tr) >> 1;
// max
push_max(t << 1, T[t].max1, tl == tm);
push_max(t << 1 | 1, T[t].max1, tm + 1 == tr);
// min
push_min(t << 1, T[t].min1, tl == tm);
push_min(t << 1 | 1, T[t].min1, tm + 1 == tr);
}
void build(int t = 1, int tl = 0, int tr = N - 1) {
if (tl == tr) {
T[t].sum = T[t].max1 = T[t].min1 = A[tl];
T[t].maxc = T[t].minc = 1;
T[t].max2 = -1e18;
T[t].min2 = 1e18;
return;
}
int tm = (tl + tr) >> 1;
build(t << 1, tl, tm);
build(t << 1 | 1, tm + 1, tr);
merge(t);
}
void update_chmin(int l, int r, ll v, int t = 1, int tl = 0, int tr = N - 1) {
if (r < tl || tr < l || v >= T[t].max1) { return; }
if (l <= tl && tr <= r && v > T[t].max2) {
push_max(t, v, tl == tr);
return;
}
pushdown(t, tl, tr);
int tm = (tl + tr) >> 1;
update_chmin(l, r, v, t << 1, tl, tm);
update_chmin(l, r, v, t << 1 | 1, tm + 1, tr);
merge(t);
}
void update_chmax(int l, int r, ll v, int t = 1, int tl = 0, int tr = N - 1) {
if (r < tl || tr < l || v <= T[t].min1) { return; }
if (l <= tl && tr <= r && v < T[t].min2) {
push_min(t, v, tl == tr);
return;
}
pushdown(t, tl, tr);
int tm = (tl + tr) >> 1;
update_chmax(l, r, v, t << 1, tl, tm);
update_chmax(l, r, v, t << 1 | 1, tm + 1, tr);
merge(t);
}
ll query_sum(int l, int r, int t = 1, int tl = 0, int tr = N - 1) {
if (r < tl || tr < l) { return 0; }
if (l <= tl && tr <= r) { return T[t].sum; }
pushdown(t, tl, tr);
int tm = (tl + tr) >> 1;
return query_sum(l, r, t << 1, tl, tm) +
query_sum(l, r, t << 1 | 1, tm + 1, tr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
N = n;
build();
for(int i=0;i<k;i++){
if(op[i] == 1)update_chmax(left[i], right[i], height[i]);
else update_chmin(left[i], right[i], height[i]);
}
for(int i=0;i<n;i++)finalHeight[i] = query_sum(i, i);
}
