[USACO07DEC] Best Cow Line G

题目背景

*本题和 [2007 年 11 月月赛银组同名题目](/problem/P6140) 在题意上一致,唯一的差别是数据范围。*

题目描述

Farmer John 打算带领 $N$($1 \leq N \leq 5 \times 10^5$)头奶牛参加一年一度的”全美农场主大奖赛“。在这场比赛中,每个参赛者必须让他的奶牛排成一列,然后带领这些奶牛从裁判面前依此走过。 今年,竞赛委员会在接受报名时,采用了一种新的登记规则:取每头奶牛名字的首字母,按照它们在队伍中的次序排成一列。将所有队伍的名字按字典序升序排序,从而得到出场顺序。 FJ 由于事务繁忙,他希望能够尽早出场。因此他决定重排队列。 他的调整方式是这样的:每次,他从原队列的首端或尾端牵出一头奶牛,将她安排到新队列尾部。重复这一操作直到所有奶牛都插入新队列为止。 现在请你帮 FJ 算出按照上面这种方法能排出的字典序最小的队列。

输入输出格式

输入格式


第一行一个整数 $N$。 接下来 $N$ 行每行一个大写字母,表示初始队列。

输出格式


输出一个长度为 $N$ 的字符串,表示可能的最小字典序队列。 每输出 $80$ 个字母需要一个换行。

输入输出样例

输入样例 #1

6
A
C
D
B
C
B

输出样例 #1

ABCBCD