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

int ilog2(int x) {
    int n = 0;
    while (x > 0) {
        x >>= 1;
        n++;
    }
    return n;
}

class fib_heap_node {
public:
    fib_heap_node *p, *left, *right, *child;
    int key, degree;
    bool mark;

    fib_heap_node(int x) {
        key = x;
        degree = 0;
        p = child = NULL;
        left = right = this;
        mark = false;
    }
};

class fib_heap {

    fib_heap_node *min;
    int size;

    void add_to_list(fib_heap_node *elem,
                     fib_heap_node *newelem) {
        if (elem == NULL)
            return;
        fib_heap_node* er = elem->right;
        newelem->right = er;
        er->left = newelem;
        elem->right = newelem;
        newelem->left = elem;
    }

    void remove_from_list(fib_heap_node *rmelem) {
        fib_heap_node *er = rmelem->right,
                      *el = rmelem->left;
        el->right = er;
        er->left = el;
    }

public:
    fib_heap() {
        size = 0;
        min = NULL;
    }

    int top() {
        return min->key;
    }

    void push(int x) {
        fib_heap_node *nx = new fib_heap_node(x);
        add_to_list(min, nx);
        if (min == NULL || min->key > x)
            min = nx;
        size++;
    }

    int pop() {
        fib_heap_node *z = min;
        int res = z->key;
        if (min != NULL) {
            fib_heap_node *mchild = z->child;
            if (mchild != NULL) {
                fib_heap_node *last = mchild->left;
                while (true) {
                    fib_heap_node *next = mchild->right;
                    add_to_list(min, mchild);
                    mchild->p = NULL;
                    if (mchild == last)
                        break;
                    mchild = next;
                }
            }
            remove_from_list(z);
            if (z == z->right)
                min = NULL;
            else {
                min = z->right;
                consolidate();
            }
            delete z;
            size--;
        }
        return res;
    }

    void consolidate() {
        int dn = ilog2(size);
        fib_heap_node *a[dn];
        for (int i = 0; i < dn; i++)
            a[i] = NULL;
        fib_heap_node *mroot = min,
                      *last = mroot->left;
        while (true) {
            fib_heap_node *x = mroot,
                          *next = mroot->right;
            int d = x->degree;
            while (a[d] != NULL) {
                fib_heap_node *y = a[d];
                if (x->key > y->key)
                        swap(x, y);
                link(y, x);
                a[d] = NULL;
                d++;
            }
            a[d] = x;
            if (mroot == last)
                break;
            mroot = next;
        }
        min = NULL;
        for (int i = 0; i < dn; i++) {
            if (a[i] != NULL) {
                a[i]->left = a[i];
                a[i]->right = a[i];
                add_to_list(min, a[i]);
                if (min == NULL || a[i]->key < min->key)
                    min = a[i];
            }
        }
    }

    void link(fib_heap_node *y,
              fib_heap_node *x) {
        remove_from_list(y);
        y->left = y->right = y;
        if (x->child != NULL)
            add_to_list(x->child, y);
        else {
            y->p = x;
            x->child = y;
        }
        x->degree++;
        y->mark = false;
    }
};

int main() {
    fib_heap h;
    srand(time(0));
    int n = 1000000;
    for (int i = 0; i < n; i++) {
        int m = rand() % 1000000000;
        //cout << m << endl;
        h.push(m);
        //if (i % 20 == 0)
            //h.consolidate();
    }
    cout << endl;
    /*
    h.push(43);
    h.push(1);
    h.push(63);
    h.push(95);
    h.push(6);*/
    for (int i = 0; i < n; i++)
        cout << h.pop() << endl;
    cout << "OK";
    return 0;
}