# include <cstdio>
# include <cmath>
# include <iostream>
# include <vector>
# include <algorithm>
# include <cstdlib>
# include <string>
# include <stack>
using namespace std;

template < typename T >

class AVL {
public:
    struct Node {
        T key;
        int height;
        Node *left;
        Node *right;
        Node(T k) {
            key = k;
            left = NULL;
            right = NULL;
            height = 1;
        }
    };
private:
    Node* root;
    vector <Node*> tree;
    int height(Node* v);
    int balanceHeight (Node* v);
    void fixHeight (Node* v);
    Node* RotateRight (Node* v);
    Node* RotateLeft (Node* v);
    Node* balance(Node* v);
    Node* FindMin(Node* v);
    Node* FindMax(Node* v);
    Node* erase_min(Node* v);
    Node* _erase(Node* v, const T& k);
    Node* findParents(Node* v, Node* w);
public:

    AVL()
    {
        root = NULL;
    };
    void insert(const T& k);
    Node* _insert(Node* v, const T& k);
    void erase(const T& k);
    Node* get_next(Node* p);
    Node* get_previous(Node* p);
    Node* get_root();
};

template < typename T >
int AVL<T>::height(Node* v){
    return v ? v->height : 0;
}

template < typename T >
int AVL<T>::balanceHeight (Node* v){
    return height(v->right) - height(v->left);
}

template < typename T >
void AVL<T>::fixHeight(Node *v) {
    int hl = height(v->left);
    int hr = height(v->right);
    v->height = max(hl, hr) + 1;
}

template < typename T >
typename AVL<T>::Node* AVL<T>::RotateRight(Node *v) {
    Node* a = v->left;
    v->left = a->right;
    a->right = v;
    fixHeight(v);
    fixHeight(a);
    return a;
}

template < typename T >
typename AVL<T>::Node* AVL<T>::RotateLeft(Node *v) {
    Node* a = v->right;
    v->right = a->left;
    a->left = v;
    fixHeight(v);
    fixHeight(a);
    return a;
}

template < typename T >
typename AVL<T>::Node* AVL<T>::balance(Node *v) {
    fixheight(v);
    if(balanceHeight(v) == 2){
        if( balanceHeight(v->right) < 0 )
            v->right = RotateRight(v->right);
        return RotateLeft(v);
    }
    if(balanceHeight()(v) == -2){
        if(balanceHeight()(v->left) < 0 )
            v->left = RotateLeft(v->left);
        return RotateRight(v);
    }
    return v;
}

template < typename T >
typename AVL<T>::Node* AVL<T>::_insert(Node *v, const T& k) {
    if(!root) {
        root = new Node(k);
        return root;
    }
    if(!v)
        return new Node(k);
    if(k < v->key)
        v->left = _insert(v->left, k);
    else
        v->right = _insert(v->right, k);
    return balance(v);
}

template < typename T >
void AVL<T>::insert(const T& k) {
    if(!root) {
        root = new Node(k);
        return;
    }
    if(k < root->key)
        root->left = _insert(root->left, k);
    else
        root->right = _insert(root->right, k);
    balance(root);
}

template < typename T >
typename AVL<T>::Node* AVL<T>::FindMin(Node* v){
    if (v->left) return FindMin(v->left);
    else return v;
}

template < typename T >
typename AVL<T>::Node* AVL<T>::FindMax(Node* v){
    if (v->right) return FindMin(v->right);
    else return v;
}

template < typename T >
typename AVL<T>::Node* AVL<T>::erase_min(Node* v) {
    if(v->left == 0)
        return v->right;
    v->left = erase_min(v->left);
    return balance(v);
}

template < typename T >
typename AVL<T>::Node* AVL<T>::_erase(Node *v, const T& k) {
    if(!v) return 0;
    if(k < v->key)
        v->left = _erase(v->left, k);
    if(v->key < k)
        v->right = _erase(v->right, k);
    if(k == v->key){
        Node* l = v->left;
        Node* r = v->right;
        delete v;
        if(!r) return l;
        Node* min = FindMin(r);
        min->right = erase_min(r);
        min->left = l;
        return balance(min);
    }
    return balance(v);
}

template < typename T >
void AVL<T>::erase(const T& k) {
    if(!root) {
        if (k < root->key)
            root->left = _erase(root->left, k);
        if (root->key < k)
            root->right = _erase(root->right, k);
        if (k == root->key) {
            Node *l = root->left;
            Node *r = root->right;
            delete root;
            if (r == NULL) {
                root = l;
                return;
            }
            if (l == NULL) {
                root = r;
                return;
            }
            Node *min = FindMin(r);
            min->right = erase_min(r);
            min->left = l;
            root = min;
            balance(root);
        }
        balance(root);
    }
    else
        root = NULL;
}

template < typename T >
typename AVL<T>::Node* AVL<T>::get_next(Node *v) {
    if( v->right != NULL )
        return FindMin(v->right);
    else {
        findParents(v, root);
        if(!tree.empty()) {
            for (int i =  tree.size() - 1; i >= 0; --i) {
                if (tree[i]->right) {
                    if (i == tree.size() - 1) {
                        if (tree[i]->right == v)
                            continue;
                    }
                    if (tree[i]->right == tree[i + 1])
                        continue;
                    return FindMin(tree[i]->right );
                }else{
                    if( v->key < tree[i]->key)
                        return tree[i];
                }
            }
        }
        return NULL;
    }
}

template < typename T >
typename AVL<T>::Node* AVL<T>::get_previous(Node *v) {
    if( v->left != NULL )
        return FindMax(v->left);
    else {
        Node* parent = findParents(v, root);
        if(!tree.empty()) {
            for (int i = tree.size() - 1; i >= 0; i--) {
                if (tree[i]->left) {
                    if (i == tree.size() - 1) {
                        if (tree[i]->left == v)
                            continue;
                    }
                    if (tree[i]->left == tree[i + 1])
                        continue;
                    return FindMax(tree[i]->left);
                }else{
                    if(tree[i]->key < v->key)
                        return tree[i];
                }
            }
        }
        return NULL;
    }
}

template < typename T >
typename AVL<T>::Node* AVL<T>::get_root() {
    return root;
}

template < typename T >
typename AVL<T>::Node* AVL<T>::findParents(Node *v, Node *w) {
    if(w == root)
        tree.clear();
    while(v != w){
        tree.push_back(w);
        if(v->key < w->key)
            w = w->left;
        else
            w = w->right;
    }
}


int main ()
{
    int n;
    cin >> n;
    vector <int> a (n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    AVL<int> Katya();
    for (int i = 0; i < n; i++)
        Katya.insert(a[i]);//Dima odobril



}