#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 3e5 + 10;
const ll INF = 1e18;

struct QueryResult {
    ll max1;
    ll max2;
    int pos_max;
    ll sum;
};

struct Node {
    int l, r;
    ll max1, max2, sum;
    int cnt_max, pos_max;
    Node() : max1(-INF), max2(-INF), sum(0), cnt_max(0), pos_max(-1) {}
} tree[4 * MAXN];

ll h[MAXN];

void pushup(int id) {
    int lc = id << 1, rc = id << 1 | 1;
    tree[id].max1 = max(tree[lc].max1, tree[rc].max1);
    tree[id].sum = tree[lc].sum + tree[rc].sum;

    if (tree[lc].max1 > tree[rc].max1) {
        tree[id].pos_max = tree[lc].pos_max;
        tree[id].cnt_max = tree[lc].cnt_max;
    } else if (tree[rc].max1 > tree[lc].max1) {
        tree[id].pos_max = tree[rc].pos_max;
        tree[id].cnt_max = tree[rc].cnt_max;
    } else {
        tree[id].pos_max = min(tree[lc].pos_max, tree[rc].pos_max);
        tree[id].cnt_max = tree[lc].cnt_max + tree[rc].cnt_max;
    }

    vector<ll> candidates;
    if (tree[lc].max1 < tree[id].max1) candidates.push_back(tree[lc].max1);
    candidates.push_back(tree[lc].max2);
    if (tree[rc].max1 < tree[id].max1) candidates.push_back(tree[rc].max1);
    candidates.push_back(tree[rc].max2);

    ll max2 = -INF;
    for (ll c : candidates) {
        if (c > max2) max2 = c;
    }
    tree[id].max2 = max2;
}

void build(int id, int l, int r) {
    tree[id].l = l;
    tree[id].r = r;
    if (l == r) {
        tree[id].max1 = h[l];
        tree[id].max2 = -INF;
        tree[id].sum = h[l];
        tree[id].cnt_max = 1;
        tree[id].pos_max = l;
        return;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    pushup(id);
}

void update(int id, int pos, ll val) {
    if (tree[id].l == tree[id].r) {
        tree[id].max1 = val;
        tree[id].sum = val;
        tree[id].max2 = -INF;
        tree[id].cnt_max = 1;
        tree[id].pos_max = pos;
        return;
    }
    int mid = (tree[id].l + tree[id].r) >> 1;
    if (pos <= mid) update(id << 1, pos, val);
    else update(id << 1 | 1, pos, val);
    pushup(id);
}

QueryResult query(int id, int l, int r) {
    if (tree[id].l >= l && tree[id].r <= r) {
        return {tree[id].max1, tree[id].max2, tree[id].pos_max, tree[id].sum};
    }
    int mid = (tree[id].l + tree[id].r) >> 1;
    QueryResult res;
    res.max1 = -INF;
    res.max2 = -INF;
    res.sum = 0;
    res.pos_max = -1;

    if (l <= mid) {
        QueryResult left = query(id << 1, l, r);
        if (left.max1 > res.max1) {
            res.max1 = left.max1;
            res.pos_max = left.pos_max;
        } else if (left.max1 == res.max1) {
            res.pos_max = min(res.pos_max, left.pos_max);
        }
        res.sum += left.sum;

        vector<ll> candidates;
        if (left.max1 < res.max1) candidates.push_back(left.max1);
        candidates.push_back(left.max2);
        for (ll c : candidates) {
            if (c > res.max2) res.max2 = c;
        }
    }
    if (r > mid) {
        QueryResult right = query(id << 1 | 1, l, r);
        if (right.max1 > res.max1) {
            res.max1 = right.max1;
            res.pos_max = right.pos_max;
        } else if (right.max1 == res.max1) {
            if (res.pos_max == -1 || right.pos_max < res.pos_max) {
                res.pos_max = right.pos_max;
            }
        }
        res.sum += right.sum;

        vector<ll> candidates;
        if (right.max1 < res.max1) candidates.push_back(right.max1);
        candidates.push_back(right.max2);
        for (ll c : candidates) {
            if (c > res.max2) res.max2 = c;
        }
    }
    return res;
}

ll sum_query(int id, int l, int r) {
    if (tree[id].l >= l && tree[id].r <= r) {
        return tree[id].sum;
    }
    int mid = (tree[id].l + tree[id].r) >> 1;
    ll sum = 0;
    if (l <= mid) sum += sum_query(id << 1, l, r);
    if (r > mid) sum += sum_query(id << 1 | 1, l, r);
    return sum;
}

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

void cut(int l, int r, int k) {
    while (k > 0) {
        QueryResult qr = query(1, l, r);
        if (qr.max1 == 0) break;

        ll t;
        if (qr.max2 == -INF) {
            t = min((ll)k, qr.max1);
        } else {
            t = min((ll)k, qr.max1 - qr.max2);
        }

        int pos = qr.pos_max;
        ll new_val = qr.max1 - t;
        update(1, pos, new_val);
        k -= t;
    }
}

void magic(int i, int x) {
    update(1, i, x);
}

long long int inspect(int l, int r) {
    return sum_query(1, l, r);
}