last

#include <iostream>
#include <vector>
using namespace std;

struct heap_elements;

struct list_segments
{
    int l;
    int r;
    int status;
    struct list_segments* next;
    struct list_segments* prev;
    int heap_ID;
};

struct heap_elements
{
    int l;
    int r;
    list_segments* to_list;
    int own_ID;
};

bool operator<(const heap_elements& a, const heap_elements& b)
{

    if ((a.r - a.l) < (b.r - b.l));
        return true;
    if ((a.r - a.l == b.r - b.l) & (a.l > b.l))
        return true;

    return false;
}

class Heap
{
    std::vector<struct heap_elements> h;
    std::vector<int> ID_to_Index;
    int heap_size;
    int current_ID;

public:
    Heap();
    bool isempty();
    heap_elements* get_top();
    void siftup();
    void siftdown(int pos);
    void swap(int i, int j);
    void add(int l, int r, list_segments* to_list);
    void delete_vertex(int ID);
    void out();
};

Heap::Heap()
{
    std::vector<struct heap_elements> h;
    heap_size = 0;
    current_ID = 0;
    std::vector<int> ID_to_Index;
}

heap_elements* Heap::get_top()
{
    return &h[0];
}

bool Heap::isempty()
{
    if (heap_size == 0)
        return true;
    return false;
}

void Heap::swap(int i, int j)
{
    heap_elements buff = h[i];
    h[i] = h[j];
    h[j] = buff;

    ID_to_Index[h[i].own_ID] = i;
    ID_to_Index[h[j].own_ID] = j;
}

void Heap::siftup()
{
    int curr = heap_size - 1;
    int parent = (curr - 1) / 2;
    while (curr > 0 & parent >= 0)
    {
        if (h[parent] < h[curr])
            swap(parent, curr);

        curr = parent;
        parent = (curr - 1) / 2;
    }
}

void Heap::siftdown(int pos)
{

    int parent, max_child;

    int curr = pos;
    int child_l = 2 * curr + 1;
    int child_r = 2 * curr + 2;

    if (h[child_r] < h[child_l])
        max_child = child_l;
    else
        max_child = child_r;

    while (child_l < heap_size)
    {
        if (child_l == heap_size - 1)
            max_child = child_l;
        else if (h[child_r] < h[child_l])
            max_child = child_l;
        else
            max_child = child_r;

        if (h[curr] < h[max_child])
            swap(curr, max_child);

        curr = max_child;
        child_l = 2 * curr + 1;
        child_r = 2 * curr + 2;
    }
}

void Heap::add(int l, int r, list_segments* to_list)
{

    heap_elements vertex;
    vertex.l = l;
    vertex.r = r;
    vertex.to_list = to_list;
    vertex.own_ID = current_ID;
    current_ID++;
    h.push_back(vertex);

    ID_to_Index.push_back(heap_size);

    heap_size++;
    siftup();
}

void Heap::delete_vertex(int ID)
{
    int pos = ID_to_Index[ID];
    swap(pos, heap_size - 1);
    h.pop_back();
    heap_size--;
    ID_to_Index[ID] = -1;
    siftdown(pos);
}

void Heap::out(void)
{

    for (int i = 0; i < heap_size; i++)
    {
        cout << "(" << h[i].l << "," << h[i].r << ") ";
    }
    cout << endl;
}

class List
{
    struct list_segments* head;
    int count;

public:
    List();
    list_segments* get_top();
    void add(int l, int r, int status, list_segments* segment, int heap_ID);
    void delete_segment(list_segments* segment);
    void add_head(int l, int r, int status, int heap_ID);
    void Print();
};

List::List()
{
    head = nullptr;
    count = 0;
}

void List::add_head(int l, int r, int status, int heap_ID)
{
    list_segments* buff = new list_segments;
    buff->prev = 0;
    buff->l = l;
    buff->r = r;
    buff->status = status;
    buff->next = head;
    buff->heap_ID = heap_ID;

    if (head != nullptr)
        head->prev = buff;

    head = buff;
    count++;
}

void List::add(int l, int r, int status, list_segments* segment, int heap_ID)
{
    list_segments* after_segment = new list_segments;
    after_segment->l = l;
    after_segment->r = r;
    after_segment->status = status;
    after_segment->next = segment->next;
    after_segment->prev = segment;
    after_segment->heap_ID = heap_ID;
    segment->next = after_segment;

    if (segment->next != nullptr)
        segment->next->prev = after_segment;

    count++;
}

void List::delete_segment(list_segments* segment)
{
    if (segment->next != nullptr)
        segment->next->prev = segment->prev;

    if (segment->prev != nullptr)
        segment->prev->next = segment->next;
    else
        head = segment->next;

    delete segment;
}

list_segments* List::get_top()
{
    return head;
}

void List::Print()
{

    list_segments* buff = head;
    while (buff->next != nullptr)
    {
        cout << "(" << buff->l << ";" << buff->status << ";" << buff->r << ")"
             << ";";
        buff = buff->next;
    }

    cout << "(" << buff->l << ";" << buff->status << ";" << buff->r << ")"
         << ";\n";
}


void find_memory(
    Heap* heap, List* List, int K, int i, std::vector<int>& answers, list_segments** requests)
{
    heap_elements* heap_top = heap->get_top();
    int answer = heap_top->l;
    if (!heap->isempty() & heap_top->r - heap_top->l > K - 2)
    {

        if (heap_top->r - heap_top->l == K - 1)
        {
            heap_top->to_list->status = 0;
            heap_top->to_list->heap_ID = -1; //Мб не нужна
            requests[i] = heap_top->to_list;
            answers.push_back(heap_top->l);
            heap->delete_vertex(heap_top->own_ID);
        }
        else
        {
            int l = heap_top->l;
            int r = l + K - 1;
            int status = 0;
            int heap_ID = -1;
            list_segments* prev_head_segment = heap_top->to_list->prev;

            heap_top->l = l + K;
            heap_top->to_list->l = l + K;

            if (heap_top->to_list->prev != nullptr)
            {
                List->add(l, r, status, prev_head_segment, heap_ID);
                requests[i] = heap_top->to_list->prev;
            }
            else
            {
                List->add_head(l, r, status, heap_ID);
                requests[i] = List->get_top();
            }
        }

        heap->siftdown(0);
        answers.push_back(answer);
    }
    else
    {
        requests[i] = nullptr;
        answers.push_back(-1);
    }
}

void free_up_memory(
    Heap* heap, List* List, int q, int i, std::vector<int>& answers, list_segments** requests)
{

    if (requests[q] != nullptr)
    {
        requests[q]->status = 1;

        if (requests[q]->prev != nullptr)
        {
            if (requests[q]->prev->status == 1 & requests[q]->prev->r == requests[q]->l - 1)
            {
                requests[q]->l = requests[q]->prev->l;
                heap->delete_vertex(requests[q]->prev->heap_ID);
                List->delete_segment(requests[q]->prev);
            }
        }

        if (requests[q]->next != nullptr)
        {
            if (requests[q]->next->status == 1 & requests[q]->next->l - 1 == requests[q]->r)
            {
                requests[q]->r = requests[q]->next->r;
                heap->delete_vertex(requests[q]->next->heap_ID);
                List->delete_segment(requests[q]->next);
            }
        }

        heap->add(requests[q]->l, requests[q]->r, requests[q]);
    }
    requests[q] = nullptr;
    requests[i] = nullptr;
}

int main()
{

    int N, M, K;

    Heap heap;
    List list;
    list_segments* requests[M];

    heap_elements* heap_top;
    std::vector<int> answers;
    list.add_head(1, N, 1, 0);
    heap.add(1, N, list.get_top());

    for (int i = 0; i < M; ++i)
    {
        cin >> K;

        if (K > 0)
            find_memory(&heap, &list, K, i, answers, requests);

        else
            free_up_memory(&heap, &list, -K - 1, i, answers, requests);
    }

    return 0;
}