#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int infi = 1e9 + 7;
struct Info {
ll sum = 0;
int mx[2]{-infi, -infi}, cnt[2]{};
Info() = default;
Info(int x) {
mx[0] = x;
mx[1] = -1e9;
cnt[0] = 1;
sum = x;
}
};
Info operator+(const Info &l, const Info &r) {
Info res{};
res.sum = l.sum + r.sum;
res.mx[0] = max(l.mx[0], r.mx[0]);
if (l.mx[0] == res.mx[0]) {
res.cnt[0] += l.cnt[0];
res.cnt[1] += l.cnt[1];
res.mx[1] = l.mx[1];
} else {
res.cnt[1] += l.cnt[0] + l.cnt[1];
res.mx[1] = l.mx[0];
}
if (r.mx[0] == res.mx[0]) {
res.cnt[0] += r.cnt[0];
res.cnt[1] += r.cnt[1];
res.mx[1] = max(res.mx[1], r.mx[1]);
} else {
res.cnt[1] += r.cnt[0] + r.cnt[1];
res.mx[1] = max(res.mx[1], r.mx[0]);
}
return res;
}
vector<Info> t;
vector<int> tag; // fill tag with 1e9+7
int sz = 1;
void tapply(int x, int tg) {
if (t[x].mx[0] > tg) {
t[x].sum -= t[x].cnt[0] * 1LL * (t[x].mx[0] - tg);
t[x].mx[0] = tg; // SEE: WE DECREASE HERE!
assert(t[x].mx[0] > t[x].mx[1]);
tag[x] = tg;
}
}
void tpush(int x) {
if (tag[x] != infi) {
for (int ch : {x * 2, x * 2 + 1}) {
tapply(ch, tag[x]);
}
tag[x] = infi;
}
}
void tpull(int x) {
t[x] = t[x << 1] + t[x << 1 | 1];
}
void rangeSetMin(int l, int r, int m, int x = 1, int lx = 0, int rx = sz) { // a[i] min= m
if (l >= rx || lx >= r || t[x].mx[0] <= m) {
return;
}
if (l <= lx && rx <= r && t[x].mx[1] < m) {
return tapply(x, m);
}
int mid = lx + rx >> 1;
tpush(x);
rangeSetMin(l, r, m, x << 1, lx, mid);
rangeSetMin(l, r, m, x << 1 | 1, mid, rx);
tpull(x);
}
int findKthMax(int l, int r, int &k, int m, int x = 1, int lx = 0, int rx = sz) { // inclusive
if (l >= rx || lx >= r || t[x].mx[0] < m) {
return -1;
}
if (l <= lx && rx <= r && t[x].cnt[0] < k) {
k -= t[x].cnt[0];
return -1;
}
if (lx + 1 == rx) {
return lx;
}
tpush(x);
int mid = lx + rx >> 1;
int res = findKthMax(l, r, k, m, x << 1, lx, mid);
if (res == -1){
res = findKthMax(l, r, k, m, x << 1 | 1, mid, rx);
}
return res;
}
Info rangeSum(int l, int r, int x = 1, int lx = 0, int rx = sz) {
if (l >= rx || lx >= r) {
return {};
}
if (l <= lx && rx <= r) {
return t[x];
}
int mid = lx + rx >> 1;
tpush(x);
return rangeSum(l, r, x << 1, lx, mid) + rangeSum(l, r, x << 1 | 1, mid, rx);
}
void modify(int i, int val, int x = 1, int lx = 0, int rx = sz) {
if (lx + 1 == rx) {
t[x] = Info(val);
return;
}
int mid = lx + rx >> 1;
tpush(x);
if (i < mid) {
modify(i, val, x << 1, lx, mid);
} else {
modify(i, val, x << 1 | 1, mid, rx);
}
tpull(x);
}
void initialise(int N, int Q, int h[]) {
sz = 1 << __lg(N) + !!(N & (N - 1));
tag.assign(sz << 1, infi);
t.assign(sz << 1, {});
for (int i = 0; i < N; ++i) {
t[i + sz] = Info(h[i + 1]);
}
for (int i = sz - 1; i > 0; --i) {
tpull(i);
}
// for (int i = 1; i < t.size(); ++i) {
// cout << t[i].sum << " ";
// }
// cout << endl;
// cerr << rangeSum(0, N).sum << endl;
}
void cut(int l, int r, int k) {
--l;
while (k > 0) {
auto info = rangeSum(l, r);
if (info.sum <= k) {
rangeSetMin(l, r, 0);
break;
}
if ((info.mx[0] - info.mx[1]) * 1LL * (info.cnt[0]) >= k) {
int full = k / info.cnt[0];
rangeSetMin(l, r, info.mx[0] - full);
k -= full * info.cnt[0];
if (k > 0) {
int p = findKthMax(l, r, k, info.mx[0] - full);
rangeSetMin(l, p + 1, info.mx[0] - full - 1);
}
break;
}
int d = (info.mx[0] - info.mx[1]) * 1LL * (info.cnt[0]);
k -= d;
rangeSetMin(l, r, info.mx[1]);
}
// Your code here.
}
void magic(int i, int x) {
--i;
modify(i, x);
// Your code here.
}
ll inspect(int l, int r) {
--l;
return rangeSum(l, r).sum;
}
