ac

# include <bits/stdc++.h>
using namespace std;

struct list_node{
    int val;
    struct list_node * next;
};


list_node * input_list(void)
{
    int n, val;
    list_node * phead = new list_node();
    list_node * cur_pnode = phead;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &val);
        if (i == 1) {
            cur_pnode->val = val;
            cur_pnode->next = NULL;
        }
        else {
            list_node * new_pnode = new list_node();
            new_pnode->val = val;
            new_pnode->next = NULL;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    return phead;
}

list_node* getSmallestNodePre(list_node *head)
{
    if(head->next == NULL){
        return NULL;
    }
    int minVal = head->val;
    list_node *minPre = NULL;

    list_node *pPre = head;
    list_node *p = head->next;
    while (p != NULL){
        list_node *pTmp = p;
        list_node *pNext = p->next;
        if(p->val < minVal){
            minPre = pPre;
            minVal = p->val;
        }
        pPre = pTmp;
        p = pNext;
    }
    return minPre;
}

list_node * selection_sort(list_node * head)
{
    //////在下面完成代码
    if(head == NULL || head->next == NULL){
        return head;
    }

    list_node *newHead = NULL;
    list_node *newTail = NULL;

    list_node *toSelectHead = head;

    while (toSelectHead != NULL){
        list_node *pre = getSmallestNodePre(toSelectHead);
        if(pre == NULL){ // 最小是 toSelectHead 的头部
            list_node *toSelectHeadNext = toSelectHead->next;

            if(newHead == NULL){
                newHead = toSelectHead;
                newTail = newHead;
                newTail->next = NULL;
            }else {
                newTail->next = toSelectHead;
                newTail = toSelectHead;
                newTail->next = NULL;
            }

            toSelectHead = toSelectHeadNext;
        }else {
            list_node *minNode = pre->next;
            pre->next = minNode->next;

            if(newHead == NULL){
                newHead = minNode;
                newTail = newHead;
                newTail->next = NULL;
            }else {
                newTail->next = minNode;
                newTail = minNode;
                newTail->next = NULL;
            }
        }
    }
    return newHead;
}

void print_list(list_node * head)
{
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    puts("");
}


int main ()
{
    list_node * head = input_list();
    list_node * new_head = selection_sort(head);
    print_list(new_head);
    return 0;
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


class Node{
    int val;
    Node next;

    public Node(int val) {
        this.val = val;
        this.next = null;
    }
}


public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static long mod = (long)Math.pow(2,29);

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        Node head = null;
        Node tail = null;
        for(int i=0;i<n;i++){
            int val = sc.nextInt();
            if(head == null){
                head = new Node(val);
                tail = head;
            }else {
                Node tmp = new Node(val);
                tail.next = tmp;
                tail = tmp;
            }
        }
        Node newHead = sortNode(head);
        printNode(newHead);
        System.out.println();
    }

    /**
     * 时间复杂度O(N), 空间复杂度O(N)
     */
    static Node sortNode(Node head){
        if(head == null || head.next == null){
            return head;
        }

        Node newHead = null;
        Node newTail = null;

        Node toSelectHead = head;

        while (toSelectHead != null){
            Node pre = getSmallestNodePre(toSelectHead);
            if(pre == null){ // 最小是 toSelectHead 的头部
                Node toSelectHeadNext = toSelectHead.next;

                if(newHead == null){
                    newHead = toSelectHead;
                    newTail = newHead;
                    newTail.next = null;
                }else {
                    newTail.next = toSelectHead;
                    newTail = toSelectHead;
                    newTail.next = null;
                }

                toSelectHead = toSelectHeadNext;
            }else {
                Node minNode = pre.next;
                pre.next = minNode.next;

                if(newHead == null){
                    newHead = minNode;
                    newTail = newHead;
                    newTail.next = null;
                }else {
                    newTail.next = minNode;
                    newTail = minNode;
                    newTail.next = null;
                }
            }
        }
        return newHead;
    }

    /**
     * 找到一个单链表中其中第一个最小节点的Pre节点，如果是head节点就返回 null
     *
     * head 一定是有至少一个节点的
     */
    static Node getSmallestNodePre(Node head){
        if(head.next == null){
            return null;
        }
        int minVal = head.val;
        Node minPre = null;

        Node pPre = head;
        Node p = head.next;
        while (p != null){
            Node pTmp = p;
            Node pNext = p.next;
            if(p.val < minVal){
                minPre = pPre;
                minVal = p.val;
            }
            pPre = pTmp;
            p = pNext;
        }
        return minPre;
    }


    static void printNode(Node node){
        if(node == null){
            return;
        }
        boolean flag = true;
        Node p = node;
        while (p != null){
            Node pNext = p.next;
            if(flag){
                System.out.print(p.val);
                flag = false;
            }else {
                System.out.print(" " + p.val);
            }
            p = pNext;
        }
    }

}
/*
5
1 3 2 4 5

1 2 3 4 5
*/