该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

小明发明了一种只用两个栈来排序的方法。他有一个存放数据的主栈和一个辅助栈，目标是将主栈中的数排成有序的状态。

题目描述

给定一个栈 $A$，其中包含 $n$ 个互不相同的整数（栈顶在输入的最后）。你有一个初始为空的辅助栈 $B$。

你的目标是通过以下操作，将栈 $A$ 中的元素按照从小到大的顺序排列（最终栈顶是最小元素，栈底是最大元素）：

1. 将 $A$ 的栈顶元素弹出并压入 $B$
2. 将 $B$ 的栈顶元素弹出并压入 $A$

请输出排序完成后栈 $A$ 从栈顶到栈底的元素顺序。

输入格式

第一行包含一个正整数 $n$（$1 \le n \le 1000$），表示栈中元素数量。

第二行包含 $n$ 个互不相同的整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^6$），其中 $a_1$ 是栈底元素，$a_n$ 是栈顶元素。

输出格式

输出一行，包含 $n$ 个整数，表示排序后从栈顶到栈底的元素顺序（即从小到大）。

样例

5
3 1 4 1 5

1 1 3 4 5

4
5 2 8 1

1 2 5 8

1
42

42