#include "weirdtree.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <cassert>
using namespace std;
struct SegmentTree {
static const int INF = 1e9;
struct Node {
int fir, sec, cnt, laz;
int64_t tot;
Node(int _fir = 0, int _sec = 0, int _cnt = 0, int _laz = INF, int64_t _tot = 0):
fir(_fir), sec(_sec), cnt(_cnt), laz(_laz), tot(_tot) {}
void apply(int x) {
if (x < fir) tot -= (int64_t) (fir - x) * cnt, fir = laz = x;
}
void push(Node &lhs, Node &rhs) {
lhs.apply(laz), rhs.apply(laz), laz = INF;
}
void pull(Node &lhs, Node &rhs) {
tot = lhs.tot + rhs.tot;
if (lhs.fir < rhs.fir) {
fir = rhs.fir;
sec = max(lhs.fir, rhs.sec);
cnt = rhs.cnt;
} else if (lhs.fir > rhs.fir) {
fir = lhs.fir;
sec = max(lhs.sec, rhs.fir);
cnt = lhs.cnt;
} else {
fir = lhs.fir;
sec = max(lhs.sec, rhs.sec);
cnt = lhs.cnt + rhs.cnt;
}
}
};
int n;
vector<Node> a;
void build(int rt, int lo, int hi, vector<int> &vec) {
if (lo == hi) a[rt] = {vec[lo], -1, 1, INF, vec[lo]};
else {
int md = (lo + hi) >> 1, lc = rt << 1, rc = lc ^ 1;
build(lc, lo, md, vec), build(rc, md + 1, hi, vec);
a[rt].pull(a[lc], a[rc]);
}
}
SegmentTree(vector<int> vec = {0, 1}) {
n = (int) vec.size() - 1;
a.resize(n * 4 + 10);
build(1, 1, n, vec);
}
void minimize(int rt, int lo, int hi, int x) {
if (a[rt].fir <= x) return;
if (a[rt].sec < x) return a[rt].apply(x);
int md = (lo + hi) >> 1, lc = rt << 1, rc = lc ^ 1;
a[rt].push(a[lc], a[rc]);
minimize(lc, lo, md, x), minimize(rc, md + 1, hi, x);
a[rt].pull(a[lc], a[rc]);
}
void traverse(int rt, int lo, int hi, int l, int r, vector<tuple<int, int, int>> &vec) {
if (l <= lo && hi <= r) return vec.emplace_back(rt, lo, hi), void();
if (hi < l || r < lo) return;
int md = (lo + hi) >> 1, lc = rt << 1, rc = lc ^ 1;
a[rt].push(a[lc], a[rc]);
traverse(lc, lo, md, l, r, vec), traverse(rc, md + 1, hi, l, r, vec);
a[rt].pull(a[lc], a[rc]);
}
void cut(int l, int r, int x) {
vector<tuple<int, int, int>> vec;
traverse(1, 1, n, l, r, vec);
while (x) {
int fir = 0, sec = 0;
const auto upd = [&fir, &sec](int val) {
if (fir == val || sec == val) return;
if (fir < val) swap(fir, val);
if (sec < val) swap(sec, val);
};
for (auto [rt, lo, hi] : vec) {
upd(a[rt].fir), upd(a[rt].sec);
}
if (fir == 0) break;
int cnt = 0;
for (auto [rt, lo, hi] : vec) if (fir == a[rt].fir) {
cnt += a[rt].cnt;
}
assert(cnt > 0);
if (cnt > x) {
for (auto [rt, lo, hi] : vec) if (fir == a[rt].fir) {
if (a[rt].cnt <= x) {
x -= a[rt].cnt;
minimize(rt, lo, hi, fir - 1);
} else {
int start_rt = rt;
while (x) {
int md = (lo + hi) >> 1, lc = rt << 1, rc = lc ^ 1;
a[rt].push(a[lc], a[rc]);
if (a[lc].fir == fir && a[lc].cnt > x) {
rt = lc, hi = md;
} else {
x -= (a[lc].fir == fir) * a[lc].cnt;
minimize(lc, lo, md, fir - 1);
rt = rc, lo = md + 1;
}
}
for (rt >>= 1; rt >= start_rt; rt >>= 1) a[rt].pull(a[rt << 1], a[rt << 1 | 1]);
break;
}
}
break;
}
if ((int64_t) (fir - sec) * cnt > x) sec = fir - x / cnt;
x -= (fir - sec) * cnt;
for (auto [rt, lo, hi] : vec) if (fir == a[rt].fir) {
minimize(rt, lo, hi, sec);
}
}
vec.clear();
traverse(1, 1, n, l, r, vec);
}
void magic(int i, int x) {
int rt = 1, lo = 1, hi = n;
while (lo < hi) {
int md = (lo + hi) >> 1, lc = rt << 1, rc = lc ^ 1;
a[rt].push(a[lc], a[rc]);
if (i <= md) rt = lc, hi = md;
else rt = rc, lo = md + 1;
}
a[rt] = {x, -1, 1, INF, x};
for (rt >>= 1; rt > 0; rt >>= 1) a[rt].pull(a[rt << 1], a[rt << 1 | 1]);
}
int64_t inspect(int l, int r) {
vector<tuple<int, int, int>> vec;
traverse(1, 1, n, l, r, vec);
int64_t res = 0;
for (auto [rt, lo, hi] : vec) res += a[rt].tot;
return res;
}
} st;
void initialise(int N, int Q, int h[]) {
st = SegmentTree(vector<int>(h, h + N + 1));
}
void cut(int l, int r, int k) {
return st.cut(l, r, k);
}
void magic(int i, int x) {
return st.magic(i, x);
}
long long int inspect(int l, int r) {
return st.inspect(l, r);
}
