#include <bits/stdc++.h>
#include "weirdtree.h"

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
using i128 = __int128;

constexpr int MAXN = 1 << 20;

int mx[MAXN], se[MAXN], cnt[MAXN], tag[MAXN], tl[MAXN], tr[MAXN];
i64 sum[MAXN];
int N;

void pull(int p) {
    if (mx[2 * p] > mx[2 * p + 1]) {
        mx[p] = mx[2 * p];
        cnt[p] = cnt[2 * p];
        se[p] = std::max(se[2 * p], mx[2 * p + 1]);
    } else if (mx[2 * p] < mx[2 * p + 1]) {
        mx[p] = mx[2 * p + 1];
        cnt[p] = cnt[2 * p + 1];
        se[p] = std::max(se[2 * p + 1], mx[2 * p]);
    } else {
        mx[p] = mx[2 * p];
        cnt[p] = cnt[2 * p] + cnt[2 * p + 1];
        se[p] = std::max(se[2 * p], se[2 * p + 1]);
    }
    sum[p] = sum[2 * p] + sum[2 * p + 1];
}

void add(int p, int v) {
    tag[p] += v;
    mx[p] -= v;
    sum[p] -= 1LL * cnt[p] * v;
}

void push(int p) {
    if (tag[p]) {
        if (mx[2 * p] == mx[p] + tag[p]) {
            add(2 * p, tag[p]);
        }
        if (mx[2 * p + 1] == mx[p] + tag[p]) {
            add(2 * p + 1, tag[p]);
        }
        tag[p] = 0;
    }
}

void modify(int p, int l, int r, int x, int y) {
    if (r - l == 1) {
        mx[p] = y;
        se[p] = -1;
        cnt[p] = 1;
        sum[p] = y;
        return;
    }
    int m = (l + r) / 2;
    push(p);
    if (x < m) {
        modify(2 * p, l, m, x, y);
    } else {
        modify(2 * p + 1, m, r, x, y);
    }
    pull(p);
}

void build(int p, int l, int r, int h[]) {
    tl[p] = l;
    tr[p] = r;
    if (r - l == 1) {
        mx[p] = h[l];
        se[p] = -1;
        cnt[p] = 1;
        sum[p] = h[l];
        return;
    }
    int m = (l + r) / 2;
    build(2 * p, l, m, h);
    build(2 * p + 1, m, r, h);
    pull(p);
}

i64 query(int p, int l, int r, int x, int y) {
    if (l >= y || r <= x) {
        return 0;
    }
    if (l >= x && r <= y) {
        return sum[p];
    }
    int m = (l + r) / 2;
    push(p);
    return query(2 * p, l, m, x, y) + query(2 * p + 1, m, r, x, y);
}

void work(int p, int l, int r, int x, int y, auto &pq) {
    if (l >= y || r <= x) {
        return;
    }
    if (l >= x && r <= y) {
        pq.push({mx[p], p});
        pq.push({se[p], p});
        return;
    }
    int m = (l + r) / 2;
    push(p);
    work(2 * p, l, m, x, y, pq);
    work(2 * p + 1, m, r, x, y, pq);
}

void chmin(int p, int l, int r, int v, int &k) {
    if (!k || v >= mx[p]) {
        return;
    }
    if (k >= cnt[p] && v > se[p]) {
        add(p, mx[p] - v);
        k -= cnt[p];
        return;
    }
    int m = (l + r) / 2;
    push(p);
    chmin(2 * p, l, m, v, k);
    chmin(2 * p + 1, m, r, v, k);
    pull(p);
}

void initialise(int N, int Q, int h[]) {
    ::N = N;
    build(1, 0, N, h + 1);
}

void cut(int l, int r, int k) {
    l--;
    k = std::min(1LL * k, query(1, 0, N, l, r));
    if (!k) {
        return;
    }
    int cur = 1E9;
    std::priority_queue<std::array<int, 2>> pq;
    work(1, 0, N, l, r, pq);
    int tot = 0;
    while (true) {
        auto [v, p] = pq.top();
        if (k < 1LL * (cur - v) * tot) {
            break;
        }
        
        pq.pop();
        k -= (cur - v) * tot;
        cur = v;
        
        if (v == mx[p]) {
            tot += cnt[p];
        } else {
            push(p);
            if (mx[2 * p] == mx[p]) {
                pq.push({se[2 * p], 2 * p});
            } else {
                pq.push({mx[2 * p], 2 * p});
                pq.push({se[2 * p], 2 * p});
            }
            if (mx[2 * p + 1] == mx[p]) {
                pq.push({se[2 * p + 1], 2 * p + 1});
            } else {
                pq.push({mx[2 * p + 1], 2 * p + 1});
                pq.push({se[2 * p + 1], 2 * p + 1});
            }
        }
    }
    
    std::vector<std::array<int, 3>> seg;
    while (!pq.empty()) {
        auto [v, p] = pq.top();
        pq.pop();
        if (mx[p] >= cur) {
            seg.push_back({tl[p], tr[p], p});
        }
    }
    std::sort(seg.begin(), seg.end());
    cur -= k / tot;
    k %= tot;
    
    for (auto [l, r, p] : seg) {
        assert(mx[p] >= cur);
        assert(se[p] < cur);
        add(p, mx[p] - cur);
        chmin(p, l, r, cur - 1, k);
    }
    for (auto [l, r, p] : seg) {
        while (p /= 2) {
            pull(p);
        }
    }
}

void magic(int i, int x) {
    i--;
    modify(1, 0, N, i, x);
}

i64 inspect(int l, int r) {
    l--;
    return query(1, 0, N, l, r);
}