#include "weirdtree.h"
#include <bit>
#include <cstdint>
#include <iostream>
#include <vector>


struct Node {
    int64_t value = 0;
    int64_t max = 0;
};
std::vector<Node> segtree;

Node Merge(Node first, Node second) {
    return {first.value + second.value, std::max(first.max, second.max)};
}
int num;


Node Insert(int left, int right, int index, int value, int value_index) {
    if (value_index < left || value_index >= right) {
        return segtree[index];
    }
    if (left + 1 == right) {
        segtree[index] = {value, value};
        return segtree[index];
    }
    int middle = (left + right) / 2;
    segtree[index] = Merge(Insert(left, middle, index*2+1, value, value_index),
                           Insert(middle, right, index*2+2, value, value_index));
    return segtree[index];
}


Node Query(int left, int right, int index, int query_left, int query_right) {
    if (query_right <= left || right <= query_left) {
        return {};
    }
    if (query_left <= left && right <= query_right) {
        return segtree[index];
    }
    int middle = (left + right) / 2;
    return Merge(Query(left, middle, index*2+1, query_left, query_right),
                 Query(middle, right, index*2+2, query_left, query_right));
}


// value, index
std::pair<int64_t, int64_t> GetMax (int left, int right, int index, int query_left, int query_right) {
    if (query_right <= left || right <= query_left) {
        return {-1, -1};
    }
    if (left + 1 == right) {
        return {segtree[index].value, left};
    }
    int middle = (left + right) / 2;
    if (query_right <= left || middle <= query_left) {
        return GetMax(middle, right, index*2+2, query_left, query_right);
    }
    if (query_right <= middle || right <= query_left) {
        return GetMax(left, middle, index*2+1, query_left, query_right);
    }
    if (segtree[index*2+1].max >= segtree[index*2+2].max) {
        return GetMax(left, middle, index*2+1, query_left, query_right);
    }
    return GetMax(middle, right, index*2+2, query_left, query_right);
}


void initialise(int N, int Q, int h[]) {
    segtree = std::vector<Node>(N*4);
    for (int i = 0; i < N; i++) {
        Insert(0, N, 0, h[i+1], i);
    }
    num = N;
}


void cut(int l, int r, int k) {
    for (int i = 0; i < k; i++) {
        std::pair<int64_t, int64_t> get_max = GetMax(0, num, 0, l-1, r);
        Insert(0, num, 0, get_max.first-1, get_max.second);
    }
}


void magic(int i, int x) {
    Insert(0, num, 0, x, i-1);
}


long long int inspect(int l, int r) {
    return Query(0, num, 0, l-1, r).value;
}