#include <iostream>
#include<cmath>
using namespace std;
struct Node {
    int x, y;
    Node* l, * r;
    Node() {
        x = NULL; y = NULL; l = NULL; r = NULL;
    }
};

void split(Node* node, int k, Node*& l, Node*& r) {
    l = r = NULL;
    if (node == NULL) return;
    if (node->x < k) {
        split(node->r, k, node->r, r);
        l = node;
    }
    else {
        split(node->l, k, l, node->l);
        r = node;
    }
}


Node* merge(Node* l, Node* r) {
    if (l == NULL) return r;
    if (r == NULL) return l;
    if (l->y > r->y) {
        l->r = merge(l->r, r);
        return l;
    }
    else {
        r->l = merge(l, r->l);
        return r;
    }
}



Node* insert(Node* t, int val) {
    Node* l, * r;
    split(t, val, l, r);
    Node* n = new Node;
    n->x = val;
    n->y = rand();
    n->l = n->r = NULL;
    n = merge(l, merge(n, r));
    return n;
}

int main() {
    Node* t=NULL;
    int n, val;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> val;
        t = insert(t, val);
    }
    return 0;
}