#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>


typedef struct Node {
    int data;
    struct Node *next, *prev;
} Node;


Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory allocation failed.\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = newNode->prev = NULL;
    return newNode;
}


void insertSorted(Node** head, int data) {
    Node* newNode = createNode(data);

    if (*head == NULL || (*head)->data >= data) {
        newNode->next = *head;
        if (*head) (*head)->prev = newNode;
        *head = newNode;
        return;
    }

    Node* current = *head;
    while (current->next && current->next->data < data) {
        current = current->next;
    }

    newNode->next = current->next;
    if (current->next) current->next->prev = newNode;
    current->next = newNode;
    newNode->prev = current;
}


void printList(Node* head) {
    while (head) {
        printf("%d", head->data);
        head = head->next;
        if (head) printf(" ");
    }
    printf("\n");
}


void freeList(Node** head) {
    Node* temp;
    while (*head) {
        temp = *head;
        *head = (*head)->next;
        free(temp);
    }
}


int isValidInput(const char* str) {
    for (int i = 0; str[i]; i++) {
        if (!isdigit(str[i]) && !isspace(str[i])) return 0;
    }
    return 1;
}

int main() {
    Node* head = NULL;
    char line[1000];
    int n, count = 0;

    
    if (!fgets(line, sizeof(line), stdin) || !isValidInput(line)) {
        printf("Invalid input.\n");
        return 0;
    }
    if (sscanf(line, "%d", &n) != 1 || n <= 0) {
        printf("Invalid input\n");
        return 0;
    }

    
    if (!fgets(line, sizeof(line), stdin) || !isValidInput(line)) {
        printf("Invalid input\n");
        return 0;
    }

    char* token = strtok(line, " \t\n\r");
    while (token) {
        insertSorted(&head, atoi(token));
        count++;
        token = strtok(NULL, " \t\n\r");
    }

    if (count != n) {
        printf("Invalid input\n");
        freeList(&head);
        return 0;
    }

    printList(head);c
    freeList(&head);
    return 0;
}