小 Z 正在玩一个卡牌游戏。他有 $N$ 张牌面朝上叠成一堆。每张卡牌上都印有一个大写英文字母。

游戏要求他将这些卡牌重新排列成新的一堆，使得新牌堆从上到下的字母序列的字典序最小。

每次操作，小 Z 只能从当前牌堆的顶部或底部取出一张牌，并将其放置在新牌堆的底部。重复此操作，直到所有卡牌都被移动到新牌堆中。

给定初始牌堆从上到下的字母序列，帮助小 Z 找到他能获得的字典序最小的序列。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 5 \times 10^5$)。

接下来的 $N$ 行，每行包含一个大写字母，表示初始牌堆中从上到下的卡牌上的字母。

输出格式

输出一个长度为 $N$ 的字符串，表示可以获得的字典序最小的序列。

样例

输入样例 1

6
B
C
B
D
C
A

输出样例 1

ABCBCD

说明

对于字符串 $s$ 和 $t$，当且仅当存在某个索引 $i$ 使得 $s_1 = t_1, s_2 = t_2, \dots, s_{i-1} = t_{i-1}$ 且 $s_i < t_i$，或者 $s$ 是 $t$ 的真前缀时，字符串 $s$ 的字典序小于字符串 $t$。字符按照字母表顺序进行比较，即 $\text{A} < \text{B} < \dots < \text{Z}$。

例如，$\text{AABC} < \text{ABCA}$，因为在第二个位置上 $\text{A} < \text{B}$。