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

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

Node* head = NULL;

// Create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = newNode->next = NULL;
    return newNode;
}

// Insert node in descending order
void insertDescending(int data) {
    Node* newNode = createNode(data);
    if (!head || data > head->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;
    newNode->prev = current;
    current->next = newNode;
}

// Delete the middle node (upper-middle for even-sized lists)
void deleteMiddle() {
    if (!head) return;

    Node* slow = head;
    Node* fast = head;

    // Fast pointer advances two steps, slow one
    while (fast && fast->next) {
        fast = fast->next->next;
        if (fast) slow = slow->next;
    }

    if (slow->prev) slow->prev->next = slow->next;
    if (slow->next) slow->next->prev = slow->prev;

    // Update head if needed
    if (slow == head) head = slow->next;

    free(slow);
}

// Print the list
void printList() {
    if (!head) {
        printf("List is empty\n");
        return;
    }

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

// Validate if a string is numeric
int isValidNumber(char* str) {
    int i = 0;
    if (str[0] == '-') i = 1;  // Allow negative numbers
    for (; str[i]; ++i) {
        if (!isdigit(str[i])) return 0;
    }
    return 1;
}

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

    char line[1000];
    if (!fgets(line, sizeof(line), stdin)) {
        printf("Invalid input\n");
        return 0;
    }

    int count = 0;
    char* token = strtok(line, " \n");
    while (token) {
        if (!isValidNumber(token)) {
            printf("Invalid input\n");
            return 0;
        }

        int value = atoi(token);
        insertDescending(value);
        count++;
        token = strtok(NULL, " \n");
    }

    deleteMiddle();
    printList();

    return 0;
}