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

struct heap_elements;

struct list_segments
{ //Структура отрезка - элемента списка отрезок

    int l;
    int r;
    int status; // Но лучше просто считать это элементов класса и делать del по указателю
    struct list_segments* next;
    struct list_segments* prev;
    int to_heap; //Указатель на себя в куче (элемент структуры heap_elements)
};

struct heap_elements
{
    int l;
    int r;
    int position;
    list_segments* to_list; //Указатель на себя в списке отрезков.
};


bool operator<(const heap_elements& a, const heap_elements& b)
{
    int len_a = a.r - a.l;
    int len_b = b.r - b.l;

    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 outHeap(); // вывод элементов кучи в форме кучи
    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 i, parent;
    i = HeapSize - 1;
    parent = (i - 1) / 2;
    while (parent >= 0 && i > 0)
    {
        if (h[parent] < h[i])
        {
            heap_elements temp = h[i];
            h[i] = h[parent];
            h[parent] = temp;
            h[i].position = i;
            h[parent].position = parent;
            h[i].to_list->to_heap = i;
            h[parent].to_list->to_heap = parent;
        }
        i = parent;
        parent = (i - 1) / 2;
    }
}

void Heap::add(heap_elements elem)
{

    h[HeapSize] = elem;
    // h[HeapSize].r = elem.r;
    // h[HeapSize].to_list=elem.to_list;
    h[HeapSize].position = HeapSize;
    h[HeapSize].to_list->to_heap = HeapSize;
    HeapSize++;
    siftup();
    /*
  parent = (i-1)/2;
  while(parent >= 0 && i > 0)  {
    if(h[i] > h[parent]) {
      int temp = h[i];
      h[i] = h[parent];
      h[parent] = temp;
    }
    i = parent;
    parent = (i-1)/2;
  }
  */
}

void Heap::siftdown(int position)
{
    int i, parent;
    int max_child;
    i = position;
    int child1 = 2 * i + 1;
    int child2 = 2 * i + 2;
    if (h[child2] < h[child1])
        max_child = child1;
    else
        max_child = child2;

    while (child1 < HeapSize)
    {
        if (child1 == HeapSize - 1)
        {
            max_child = child1;
        }
        else if (h[child2] < h[child1])
            max_child = child1;
        else
            max_child = child2;

        if (h[i] < h[max_child])
        {
            heap_elements temp = h[i];
            h[i] = h[max_child];
            h[max_child] = temp;
            h[i].position = i;
            h[max_child].position = max_child;
            h[i].to_list->to_heap = i;
            h[max_child].to_list->to_heap = max_child;
        }
        i = max_child;
        child1 = 2 * i + 1;
        child2 = 2 * i + 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 SEGMENT BEGIN -----------------------------------------
class LIST_SEGMENTS
{
    struct list_segments *Head, *Tail;
    struct list_segments* element;
    int Count;

public:
    LIST_SEGMENTS(); // конструктор кучи
    // LIST_SEGMENTS(int, int, int, struct list_segments*, struct list_segments*,int); //
    // конструктор кучи
    void add(int, int, int, list_segments*, int);
    void delete_segment(list_segments*);
    void Print();
    void add_head(int, int, int, int);
    list_segments* get_head();
    // void out(); // вывод элементов кучи в форме массива
};

LIST_SEGMENTS::LIST_SEGMENTS()
{
    // Изначально список пуст
    Head = Tail = NULL;
    Count = 0;
}
void LIST_SEGMENTS::add_head(int l, int r, int status, int to_heap)
{
    // новый элемент
    list_segments* temp = new list_segments;

    // Предыдущего нет
    temp->prev = 0;
    // Заполняем данные
    temp->l = l;
    temp->r = r;
    temp->status = status;
    // Следующий - бывшая голова
    temp->next = Head;

    // Если элементы есть?
    if (Head != 0)
        Head->prev = temp;

    // Если элемент первый, то он одновременно и голова и хвост
    if (Count == 0)
        Head = Tail = temp;
    else
        // иначе новый элемент - головной
        Head = temp;

    Count++;
}

/*
LIST_SEGMENTS::LIST_SEGMENTS(struct list_segments* segment,int l, int r, int status, struct
list_segments* next, struct list_segments* prev,
    int to_heap)
{
    segment = new list_segments;
    segment.l = l;
    segment.r = r;
    segment.status = status;
    segment.next = next;
    segment.prev = prev;
    segment.to_heap = to_heap;
}
*/

void LIST_SEGMENTS::add(int l, int r, int status, list_segments* segment, int to_heap)
{
    // struct list_segments* next;
    // struct list_segments* prev;
    // prev = segment;
    //*next = &(segment->next);
    list_segments* segment2 = new list_segments;
    // LIST_SEGMENTS(elem,l, r, status, &(segment->next), &segment, to_heap);
    segment2->l = l;
    segment2->r = r;
    segment2->status = status;
    segment2->next = segment->next;
    segment2->prev = segment;
    segment2->to_heap = to_heap;
    if (segment->next != NULL)
        segment->next->prev = segment2;
    segment->next = segment2;
    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; // или free или любое другое удаление хзхзхз
}
void LIST_SEGMENTS::Print()
{
    // Если в списке присутствуют элементы, то пробегаем по нему
    // и печатаем элементы, начиная с головного
    list_segments* temp = Head;
    cout << "( ";
    while (temp->next != NULL)
    {
        cout << temp->l << ", " << temp->r << ";";
        temp = temp->next;
    }

    cout << temp->l << "," << temp->r << " )\n";
}
list_segments* LIST_SEGMENTS::get_head()
{
    return Head;
}

// LIST SEGMENT END

int main()
{

    //-------------------------------------------------------- REAL ЗАГАТОВКА
    //Массив указателей на отрезки (list_segments)


    Heap heap;

    int N, M, K;

    cout << "Enter N: " ;
    cin >> N;


    // Узнали N, можно добавить весь массив в структуры данных

    //Создание вершины и добавление в кучу
    heap_elements vertex;
    vertex.l = 1;
    vertex.r = N;
    vertex.to_list = NULL;
    vertex.position = 0;
    cout << "1" << endl;
    heap.add(vertex);
    cout << "1" << endl;
    // Cоздание списка отрезков
    list_segments segment; //Создаем отрезок-структуру, заполняем
    segment.l = 1;
    segment.r = N;
    segment.status = 1;
    // segment.position = 0; //Не надо, можно просто удалять
    segment.next = NULL;
    segment.prev = NULL;
    segment.to_heap = 0; //?????????????

    LIST_SEGMENTS List; //Создаём пустой двусязный список
    List.add_head(1, N, 1, 0);
    vertex.to_list = List.get_head(); //Записываем в вершину запись её копии в списке отрезков
    //(можно ли это сделать просто &segment?)


    heap_elements heap_head;
    cout << "Enter M: " ;
    cin >> M;
    list_segments* requests[M];
    for (int i = 0; i < M; ++i)
    { //Обрабатываем запросы

        cout << "Enter K: " ;
        cin >> K;

        if (K > 0)
        {

            heap_head = heap.get_head();
            if ((heap_head.r - heap_head.l + 1) >= K)
            {

                //Меняем значение у структуры в вершине на [l+K,r]
                int old_l = heap_head.l;
                heap_head.l = old_l + K;

                //о указателю из структуры в вершине находим отрезок [l,r] списка отрезков, меняем
                //его на [l+K,r]
                heap_head.to_list->l = old_l + K;

                //Создаём перед отрезком новый элемент списка [l,l+K−1], status=0, указатель пустой.
                //Написать класс  и просто делать init
                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, heap_head.to_list->prev, -1);
                    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 << old_l;
            }
            else
            {
                requests[i] = NULL;
                cout << -1 << endl;
            }
        }

        else
        {
            int q = abs(K) - 1;
            if (requests[q] != NULL)
            {
                //Получаем по указателю из (q−1)-го элемента массива запросов адрес занятого отрезка
                //в списке.
                //Меняем status с 0 на 1.
                requests[q]->status = 1;


                //Смотрим на отрезки слева и справа от освобожденного отрезка. Если отрезки идут
                //подряд (один или оба),
                //то по указателям находим их в куче (один или оба) и удаляем, затем объединяем их в
                //один.

                if (requests[q]->prev != NULL & 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 & 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 = heap_elements(requests[q].l, requests[q].r, *requests[q]);
                    vertex.l = requests[q]->l;
                    vertex.r = requests[q]->r;
                    vertex.to_list = requests[q];
                    vertex.position = 0;  //заполнится само
                    heap.add(vertex);


                //Указатель нового отрезка в списке приравниваю к адресу созданного
                //элемента структуры.
                //requests[q].to_heap = &vertex; Сделается автоматически кучей в Add и Siftup

            }

            else
            {
                requests[i] = NULL;
            }
        }

    cout << "Запрос ------ " << M << "\n";
    heap.out();
    List.Print();
    cout << "------ \n";
    }

    return 0;
}