#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3F3F3F3F
struct DATA
{
long long mx1 = -inf, mx2 = -inf, cnt = 0, s = 0;
};
const long long MXN = 3e5 + 5;
long long n;
long long arr[MXN];
DATA st[MXN << 2];
DATA combine(DATA x, DATA y)
{
if (x.mx1 == y.mx1) return {x.mx1, max(x.mx2, y.mx2), x.cnt + y.cnt, x.s + y.s};
else if (x.mx1 > y.mx1) return {x.mx1, max(x.mx2, y.mx1), x.cnt, x.s + y.s};
else return {y.mx1, max(x.mx1, y.mx2), y.cnt, x.s + y.s};
}
void build(long long l, long long r, long long x)
{
if (l == r)
{
st[x] = {arr[l], -inf, 1, arr[l]};
return;
}
long long mid = (l + r) >> 1;
build(l, mid, 2*x);
build(mid + 1, r, 2*x + 1);
st[x] = combine(st[2*x], st[2*x + 1]);
}
void relax(long long x, long long val)
{
if (st[x].mx1 > val)
{
st[x].s -= (st[x].mx1 - val) * st[x].cnt;
st[x].mx1 = val;
}
}
void upd(long long l, long long r, long long x, long long lx, long long rx, long long val)
{
if (lx > rx) return;
relax(x, st[x / 2].mx1);
if (l > rx || r < lx) return;
if (st[x].mx1 <= val) return;
if (!(l >= lx && r <= rx) || st[x].mx2 >= val)
{
long long mid = (l + r) >> 1;
upd(l, mid, 2*x, lx, rx, val);
upd(mid + 1, r, 2*x + 1, lx, rx, val);
st[x] = combine(st[2*x], st[2*x + 1]);
}
else relax(x, val);
}
void make(long long l, long long r, long long x, long long ind)
{
relax(x, st[x / 2].mx1);
if (!(l <= ind && ind <= r)) return;
if (l == r)
{
st[x] = {arr[l], -inf, 1, arr[l]};
return;
}
long long mid = (l + r) >> 1;
make(l, mid, 2*x, ind);
make(mid + 1, r, 2*x + 1, ind);
st[x] = combine(st[2*x], st[2*x + 1]);
}
long long gets(long long l, long long r, long long x, long long lx, long long rx)
{
if (lx > rx) return 0;
if (l > rx || r < lx) return 0;
relax(x, st[x / 2].mx1);
if (l >= lx && r <= rx) return st[x].s;
long long mid = (l + r) >> 1;
return gets(l, mid, 2*x, lx, rx) + gets(mid + 1, r, 2*x + 1, lx, rx);
}
DATA get(long long l, long long r, long long x, long long lx, long long rx)
{
if (lx > rx) return {-inf, -inf, 0, 0};
if (l > rx || r < lx) return {-inf, -inf, 0, 0};
relax(x, st[x / 2].mx1);
if (l >= lx && r <= rx) return st[x];
long long mid = (l + r) >> 1;
return combine(get(l, mid, 2*x, lx, rx), get(mid + 1, r, 2*x + 1, lx, rx));
}
array<long long, 2> findkthval(long long l, long long r, long long x, long long lx, long long rx, long long k, long long val)
{
if (lx > rx) return {-1, 0};
if (l > rx || r < lx) return {-1, 0};
relax(x, st[x / 2].mx1);
if (l >= lx && r <= rx && (st[x].mx1 != val || st[x].cnt < k)) return {-1, 1LL * (st[x].mx1 == val) * st[x].cnt};
if (l == r) return {l, 1LL * (st[x].mx1 == val) * st[x].cnt};
long long mid = (l + r) >> 1;
array<long long, 2> A = findkthval(l, mid, 2*x, lx, rx, k, val);
if (A[0] != -1) return A;
return findkthval(mid + 1, r, 2*x + 1, lx, rx, k - A[1], val);
}
void initialise(int N, int Q, int h[])
{
for (long long i = 1; i <= N; i++) arr[i] = h[i];
n = N;
st[0] = {inf, inf, 0, 0};
build(1, n, 1);
}
void cut(int l, int r, int K)
{
long long k = K;
while (1)
{
DATA x = get(1, n, 1, l, r);
if (x.mx1 == 0) return;
long long lw = max(0LL, x.mx2);
if ((x.mx1 - lw) * x.cnt > k) break;
upd(1, n, 1, l, r, lw);
k -= (x.mx1 - lw) * x.cnt;
}
if (!k) return;
DATA x = get(1, n, 1, l, r);
if (x.mx1 == 0) return;
array<long long, 2> q = findkthval(1, n, 1, l, r, (k - 1) % x.cnt + 1, x.mx1);
upd(1, n, 1, l, q[0], x.mx1 - ((k + x.cnt - 1) / x.cnt));
upd(1, n, 1, q[0] + 1, r, x.mx1 - (k / x.cnt));
}
void magic(int i, int x)
{
arr[i] = x;
make(1, n, 1, i);
}
long long int inspect(int l, int r)
{
return gets(1, n, 1, l, r);
}
