program-7.cpp

/* 
Treap Implementation
*/

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

class Node {
public:
    int key, priority;
    Node *left, *right;

    Node(int k) {
        key = k;
        priority = rand();
        left = right = NULL;
    }
};

Node* rightRotate(Node* y) {
    Node* x = y->left;
    y->left = x->right;
    x->right = y;
    return x;
}

Node* leftRotate(Node* x) {
    Node* y = x->right;
    x->right = y->left;
    y->left = x;
    return y;
}

Node* insert(Node* root, int key) {
    if (!root)
        return new Node(key);

    if (key <= root->key) {
        root->left = insert(root->left, key);

        if (root->left->priority > root->priority)
            root = rightRotate(root);
    } else {
        root->right = insert(root->right, key);

        if (root->right->priority > root->priority)
            root = leftRotate(root);
    }

    return root;
}

void inorder(Node* root) {
    if (root) {
        inorder(root->left);
        cout << root->key << " ";
        inorder(root->right);
    }
}

int main() {
    Node* root = NULL;

    int n, x;
    cin >> n;

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

    inorder(root);

    return 0;
}