#include <iostream>
using namespace std;

struct heap_elements;

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

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


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
{
    static const int SIZE = 100;
    struct heap_elements* h;
    int HeapSize;
public:
    Heap();
    void add(heap_elements);
    void out();
    void siftup();
    void siftdown(int);
    void delete_vertex(int);
    heap_elements* get_head();
};

Heap::Heap()
{
    h = new heap_elements[SIZE];
    HeapSize = 0;
}

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

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

            h[curr].position = curr;
            h[parent].position = parent;

            h[curr].to_list->to_heap = curr;
            h[parent].to_list->to_heap = parent;
        }
        curr = parent;
        parent = (curr - 1) / 2;
    }
}

void Heap::add(heap_elements vertex)
{

    h[HeapSize] = vertex;
    h[HeapSize].position = HeapSize;

    if (h[HeapSize].to_list != NULL)
        h[HeapSize].to_list->to_heap = HeapSize;

    HeapSize++;
    siftup();
}

void Heap::siftdown(int position)
{
    int curr, parent,max_child;
    curr = position;

    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 < HeapSize)
    {
        if (child_l == HeapSize - 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])
        {
            heap_elements buff = h[curr];
            h[curr] = h[max_child];
            h[max_child] = buff;

            h[curr].position = curr;
            h[max_child].position = max_child;

            h[curr].to_list->to_heap = curr;
            h[max_child].to_list->to_heap = max_child;
        }

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

void Heap::delete_vertex(int position)
{
    h[position] = h[HeapSize - 1];
    h[HeapSize - 1].l = 0;
    h[HeapSize - 1].r = 0;
    HeapSize--;
    siftdown(position);
}

void Heap::out(void)
{

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

//----------------------------------------------------------------LIST SEGMENTS BEGIN
class LIST_SEGMENTS
{
    struct list_segments *Head;
    struct list_segments* element;
    int Count;

public:
    LIST_SEGMENTS();
    void add(int, int, int, int, list_segments*);
    void delete_segment(list_segments*);
    void Print();
    void add_head(int, int, int, int);
    list_segments* get_head();

};

LIST_SEGMENTS::LIST_SEGMENTS()
{
    Head = NULL;
    Count = 0;
}
void LIST_SEGMENTS::add_head(int l, int r, int status, int to_heap)
{

    list_segments* buff = new list_segments;

    buff->prev = 0;
    buff->l = l;
    buff->r = r;
    buff->status = status;
    buff->next = Head;

    if (Head != NULL)
        Head->prev = buff;

    /*
    if (Count == 0)
        Head = buff;  // ----------------------------------------???
    else
        Head = buff;
    */
    Head = buff;

    Count++;
}


void LIST_SEGMENTS::add(int l, int r, int status, int to_heap, list_segments* segment)
{

    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->to_heap = to_heap;
    if (segment->next != NULL)
        segment->next->prev = after_segment;
    segment->next = after_segment;
    Count++;
}

void LIST_SEGMENTS::delete_segment(list_segments* segment)
{
    if (segment->next != NULL)
        segment->next->prev = segment->prev;
    if (segment->prev != NULL)
        segment->prev->next = segment->next;
    else
        Head = segment->next;
    delete segment;
}

void LIST_SEGMENTS::Print()
{


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

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

list_segments* LIST_SEGMENTS::get_head()
{
    return Head;
}

int main()
{

    int N1,N2,N3,N4,N5;
    int M1,M2,M3,M4,M5;

    //отказ -1
    //освободили -2
    //нечего освобождать -3

    N1 = 6; M1 = 8;
    int req_mas1[] = {2,3,-1,3,3,-5,2,2};
    int true_answer_mas1[] = {1,3,-2,-1,-1,-3,1,-1};

    N2 = 1; M2 = 7;
    int req_mas2[] = {2,2,1,1,-4,-1,-3}; //answer = -1 -1 1 -1 none none free
    int true_answer_mas2[] = {-1,-1,1,-1,-3,-3,-2};

    N3 = 6; M3 = 6;
    int req_mas3[] = {2,2,2,-1,-3,-2};  //Тест со слиянием answer 1 3 5 free free free
    int true_answer_mas3[] = {1,3,5,-2,-2,-2};

    /*
    N4 = 6; M4 = 8;
    int req_mas4[] = {2,3,-1,3,3,-5,2,2};

    N5 = 6; M5 = 8;
    int req_mas5[] = {2,3,-1,3,3,-5,2,2};
    */


    Heap heap;

    int N, M, K;

    //Записываю данные для теста
    N = N1;
    M = M1;
    int req[M];
    int answer_mas[M];
    int true_answer_mas[M];
    for (int j=0; j < M; ++j) {
        req[j] = req_mas1[j];
        answer_mas[j] = -1;
        true_answer_mas[j] = true_answer_mas1[j];
    }

    cout << "N,M = " << N << " " << M << endl;
    //cout << "Enter N: ";
    //cin >> N;

    heap_elements vertex;
    vertex.l = 1;
    vertex.r = 6;
    vertex.to_list = NULL;
    vertex.position = 0;

    LIST_SEGMENTS List;
    List.add_head(1, N, 1, 0);

    vertex.to_list = List.get_head();
    heap.add(vertex);

    list_segments segment;
    heap_elements* heap_head;
    //cout << "Enter M: ";
    //cin >> M;

    list_segments* requests[M];
    for (int i = 0; i < M; ++i)
    {

        K = req[i];
        cout << "\n ЗАПРОС НОМЕР " << i <<  " Enter K: " << K << endl;
        //cin >> K;

        if (K > 0)
        {

            heap_head = heap.get_head();
            if ((heap_head->r - heap_head->l + 1) >= K)
            {
                if ((heap_head->r - heap_head->l + 1) == K){
                    heap_head->to_list->status=0;
                    requests[i] = heap_head->to_list;
                    cout << "ANSWER:" << heap_head->l << endl;
                    answer_mas[i] = heap_head->l;
                    heap.delete_vertex(0);
                }
                else{
                    //cout << "Можем откусить \n" << endl;

                    int old_l = heap_head->l;
                    heap_head->l = old_l + K;
                    //cout << "Изменившаяся куча после откусывания: " <<heap_head->l<< "\n";




                    heap_head->to_list->l = old_l + K;



                    segment.l = old_l;
                    segment.r = old_l + K - 1;
                    segment.status = 0;
                    segment.to_heap = -1;

                    if (heap_head->to_list->prev != NULL)
                    {
                        List.add(old_l, old_l + K - 1, 0, -1,heap_head->to_list->prev);
                        requests[i] = heap_head->to_list->prev;
                    }
                    else
                    {
                        List.add_head(old_l, old_l + K - 1, 0, -1);
                        requests[i] = List.get_head();
                    }



                    heap.siftdown(0);

                    cout << "ANSWER: " << old_l << endl;
                    answer_mas[i] = old_l;
                }
            }
            else
            {
                requests[i] = NULL;
                cout << "ANSWER:" << -1 << endl;
                answer_mas[i] = -1;
            }
        }

        else
        {
            int q = abs(K) -1;
            if (requests[q] != NULL)
            {

                requests[q]->status = 1;

                if (requests[q]->prev != NULL){
                    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->to_heap);
                        List.delete_segment(requests[q]->prev);
                    }
                }
                if (requests[q]->next != NULL){
                    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->to_heap);
                        List.delete_segment(requests[q]->next);
                    }
                }

                    vertex.l = requests[q]->l;
                    vertex.r = requests[q]->r;
                    vertex.to_list = requests[q];
                    vertex.position = 0;
                    heap.add(vertex);

                requests[i] = requests[q];
                requests[q] = NULL;
                cout << "Освободили"  << endl;
                answer_mas[i] = -2;
            }

            else
            {
                cout << "Не было занято, поэтому не освободили"  << endl;
                requests[i] = NULL;
                answer_mas[i] = -3;
            }


        }

    cout << "Куча после запроса: ";
    heap.out();
    cout << "List после запроса: ";
    List.Print();
    cout << "requests после запроса i: ";
    for (int f=0; f < i+1; ++f)
        if (requests[f] == NULL)
            cout << " null; ";
        else
            cout << "(" << requests[f]->l << ";" << requests[f]->status << ";"  << requests[f]->r << ")"<< "; ";
    cout << "\n---------------";
    }

    cout << "\n answer_mas      = ";
    for (int i=0; i < M; ++i) {
        cout << answer_mas[i] << " ";
    }
    cout << endl;

    cout << "true answer_mas  = ";
    for (int i=0; i < M; ++i) {
        cout << true_answer_mas[i] << " ";
    }

    return 0;
}