#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::Heap()
{
    h = new heap_elements[SIZE];
    HeapSize = 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;
        }
        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;
    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;
        }
        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)
    vector<list_segments*> requests;

    Heap heap;

    int N,M,K;


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

    //Создание вершины и добавление в кучу
    heap_elements vertex;
    vertex.l = 1;
    vertex.r = N;
    vertex.to_list = NULL;
    vertex.position = 0;
    heap.add(vertex);

    //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.out();
    List.Print();

    return 0;
}