#include <stdio.h>
#include <stdlib.h>
#define max(a, b) ((a < b) ? b : a)

struct node {

    int key;
    int height;
    struct node *left;
    struct node *right;
};

typedef struct node avl_node;

avl_node* create_node(const int key) {

    avl_node *node = malloc(sizeof(avl_node));
    node->key = key;
    node->height = 0;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int height_node(avl_node *root) {

    int left_height = ((root->left != NULL) ? root->left->height : 0);
    int right_height = ((root->right != NULL) ? root->right->height : 0);
    return max(left_height, right_height) + 1;
}

avl_node* r_rotation(avl_node *root) {

    avl_node *temp = root->left;
    root->left = temp->right;
    temp->right = root;
    root->height = height_node(root);
    return temp;
}

avl_node* l_rotation(avl_node *root) {

    avl_node *temp = root->right;
    root->right = temp->left;
    temp->left = root;
    root->height = height_node(root);
    return temp;
}

avl_node* rl_rotation(avl_node *root) {

    root->right = r_rotation(root->right);
    return l_rotation(root);
}

avl_node* lr_rotation(avl_node *root) {

    root->left = l_rotation(root->left);
    return r_rotation(root);
}

avl_node* balance(avl_node* root) {

    int left_height = ((root->left != NULL) ? root->left->height : 0);
    int right_height = ((root->right != NULL) ? root->right->height : 0);

    if (right_height - left_height > 1) {

        avl_node *node = root->right;
        int rl_height = ((node->left != NULL) ? node->left->height : 0);
        int rr_height = ((node->right != NULL) ? node->right->height : 0);
        if (rr_height > rl_height)
            root = l_rotation(root);
        else
            root =  rl_rotation(root);
    }

    if (left_height - right_height > 1) {

        avl_node *node = root->left;
        int ll_height = ((node->left != NULL) ? node->left->height : 0);
        int lr_height = ((node->right != NULL) ? node->right->height : 0);
        if (ll_height > lr_height)
            root = r_rotation(root);
        else
            root = lr_rotation(root);
    }
    root->height = height_node(root);
    return root;
}


avl_node* insert(avl_node *root, const int key) {

    if (root == NULL)
        root = create_node(key);
    else {

        if (key < root->key)
            root->left = insert(root->left, key);
        else
            root->right = insert(root->right, key);
    }
    return balance(root);
}

void srd_tree(FILE *file, avl_node* root) {

    if (root != NULL) {

        if (root->left != NULL)
            srd_tree(file, root->left);
        fprintf(file, "%d ", root->key);
        if (root->right != NULL)
            srd_tree(file, root->right);
    }
}

int main(int argc, char *argv[]) {

    int n, x, i;
    FILE *in = fopen("algsort.in", "r");
    fscanf(in, "%d", &n);

    avl_node *head = NULL;

    for (i = 1; i <= n; ++i) {

        fscanf(in, "%d", &x);
        head = insert(head, x);
    }
    fclose(in);

    FILE *out = fopen("algsort.out", "w");
    srd_tree(out, head);
    fclose(out);

    return 0;
}