#include <iostream>
#include <cstdio>
#include <time.h>
#include <stdlib.h>
#define inf 0x3f3f3f

using namespace std;

struct treapNode
{
    int key, priority;
    treapNode *left, *right;
    treapNode() {};
    treapNode(int key, int priority, treapNode *left, treapNode *right)
    {
        this->key = key;
        this->priority = priority;
        this->left = left;
        this->right = right;
    }
}*R, *nil;

void initialize(treapNode* &R)
{
    srand(unsigned(time(0)));
    R = nil = new treapNode(0, 0, NULL, NULL);
}

void rotateLeft(treapNode* &n)
{
    treapNode *t = n->left;
    n->left = t->right;
    t->right = n;
    n = t;
}

void rotateRight(treapNode* &n)
{
    treapNode *t=n->right;
    n->right = t->left;
    t->left = n;
    n = t;
}

void balance(treapNode* &n)
{
    if(n->left->priority > n->priority)
        rotateLeft(n);
    else if(n->right->priority > n->priority)
        rotateRight(n);
}

void insertNode(treapNode* &n, int key, int priority)
{
    if(n == nil){
        n = new treapNode(key, priority, nil, nil);
        return;
    }
    if(key < n->key)
        insertNode(n->left, key, priority);
    else if(key > n->key)
        insertNode(n->right, key, priority);

    balance(n);

}

bool searchNode(treapNode* n, int key)
{
    if(n == nil) return false;
    if(n->key == key) return true;
    if(key < n->key)
        return searchNode(n->left, key);
    else
        return searchNode(n->right, key);
}

void eraseNode(treapNode* &n, int key)
{
    if(n == nil) return;

    if(key < n->key)
        return eraseNode(n->left, key);
    else if(key > n->key)
        return eraseNode(n->right, key);
    else
    {
        if(n->left == nil && n->right == nil)
            delete n, n = nil;
        else (n->left->priority > n->right->priority)? rotateLeft(n) : rotateRight(n);
        eraseNode(n, key);
    }
}

void split(treapNode* &R, treapNode* &Ts, treapNode* &Tg, int key)
{
    insertNode(R, key, inf);
    Ts = R->left;
    Tg = R->right;
    delete R, R=nil;
}

void join(treapNode* &R, treapNode* &Ts, treapNode* &Tg, int key)
{
    R = new treapNode(key, 0, Ts, Tg);
    eraseNode(R, R->key);
}

void read()
{
    int n, key;
    scanf("%d", &n);
    for(int i=1; i<=n; ++i)
    {
        scanf("%d", &key);
        insertNode(R, key, rand()+1);
    }

}

int main()
{
    freopen("treap.in", "r", stdin);
    initialize(R);
    read();
    return 0;
}