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

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

Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->prev = newNode->next = NULL;
    return newNode;
}

int main() {
    int n;
    if (scanf("%d", &n) != 1 || n < 1 || n > 1000) {
        printf("Invalid input");
        return 0;
    }

    Node *head = NULL, *tail = NULL;

    for (int i = 0; i < n; i++) {
        char str[50];
        scanf("%s", str);

        // Validation: only digits allowed
        for (int j = 0; str[j] != '\0'; j++) {
            if (!isdigit(str[j])) {
                printf("Invalid input");
                return 0;
            }
        }

        int val = atoi(str);
        Node* newNode = createNode(val);

        if (!head) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
    }

    // Sorting using simple bubble sort on linked list
    Node *temp, *index;