#include <cstdio>

#define max(a, b) ((a) > (b) ? (a) : (b))
#define getHeight(parent) (parent -> height = 1 + max(parent -> son[left] -> height, parent -> son[right] -> height))

enum {left, right};

struct avlNode
{
    int data;
    char height;
    avlNode *son[2];

    avlNode(int _data, int _height, avlNode *_son)
    {
        data = _data;
        height = _height;
        son[left] = son[right] = _son;
    }
};

class AVL
{

private:

    avlNode *root, *NIL;

    avlNode* rotate(avlNode *parent, bool direction)
    {
        avlNode *newParent = parent -> son[!direction];

        parent -> son[!direction] = newParent -> son[direction];
        newParent -> son[direction] = parent;

        getHeight(parent);
        getHeight(newParent);

        return newParent;
        }

    avlNode* balance(avlNode* parent)
    {
        getHeight(parent);

        if(parent -> son[left] -> height > parent -> son[right] -> height + 1)
        {
            if(parent -> son[left] -> son[right] -> height > parent -> son[left] -> son[left] -> height)
            {
                parent -> son[left] = rotate(parent -> son[left], left);
            }
            parent = rotate(parent, right);
        }
        else if(parent -> son[right] -> height > parent -> son[left] -> height + 1)
        {
            if(parent -> son[right] -> son[left] -> height > parent -> son[right] -> son[right] -> height)
            {
                parent -> son[right] = rotate(parent -> son[right], right);
            }
            parent = rotate(parent, left);
        }

        return parent;
    }

    avlNode* _insert(avlNode *parent, int data)
    {
        if(parent == NIL) return new avlNode(data, 0, NIL);

        if(data < parent -> data) parent -> son[left] = _insert(parent -> son[left], data);
        else parent -> son[right] = _insert(parent -> son[right], data);

        return balance(parent);
    }

    void dfs(avlNode *parent, int dfsType)
    {
        if(parent == NIL) return;

        if(dfsType == 1) printf("%d ", parent -> data);

        dfs(parent -> son[left], dfsType);

        if(dfsType == 2) printf("%d ", parent -> data);

        dfs(parent -> son[right], dfsType);

        if(dfsType == 3) printf("%d ", parent -> data);
    }

public:

    AVL()
    {
        root = NIL = new avlNode(0, -1, NULL);
    }

    void insert(int data)
    {
        root = _insert(root, data);
    }

    void inorder()
    {
        dfs(root, 2);
        printf("\n");
    }
};

int main() {

    freopen("algsort.in", "r", stdin);
    freopen("algsort.out", "w", stdout);

    int N, number;
    AVL input;

    scanf("%d", &N);

    for(int i = 1; i <= N; i++)
    {
        scanf("%d", &number);
        input.insert(number);
    }

    input.inorder();

    return 0;
}