program-8.cpp

/* 
Skip List Implementation
*/

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

const int MAXLVL = 3;

class Node {
public:
    int val;
    Node* forward[MAXLVL + 1];

    Node(int v) {
        val = v;

        for (int i = 0; i <= MAXLVL; i++)
            forward[i] = NULL;
    }
};

class SkipList {
    Node* header;
    int level;

public:
    SkipList() {
        level = 0;
        header = new Node(-1);
    }

    int randomLevel() {
        int lvl = 0;

        while (rand() % 2 && lvl < MAXLVL)
            lvl++;

        return lvl;
    }

    void insert(int val) {
        Node* update[MAXLVL + 1];
        Node* cur = header;

        for (int i = level; i >= 0; i--) {
            while (cur->forward[i] && cur->forward[i]->val < val)
                cur = cur->forward[i];

            update[i] = cur;
        }

        cur = cur->forward[0];

        if (!cur || cur->val != val) {
            int rlevel = randomLevel();

            if (rlevel > level) {
                for (int i = level + 1; i <= rlevel; i++)
                    update[i] = header;

                level = rlevel;
            }

            Node* n = new Node(val);

            for (int i = 0; i <= rlevel; i++) {
                n->forward[i] = update[i]->forward[i];
                update[i]->forward[i] = n;
            }
        }
    }

    void display() {
        Node* node = header->forward[0];

        while (node) {
            cout << node->val << " ";
            node = node->forward[0];
        }
    }
};

int main() {
    SkipList s;

    int n, x;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> x;
        s.insert(x);
    }

    s.display();

    return 0;
}