X龙珠

题目描述

“X龙珠”是一款益智小游戏。游戏中有 $n(2|n)$ 个编号互不相同龙珠按照给定的顺序排成一个队列,每个龙珠上面都有一个编号。每次操作时,选择并取出龙珠队列中**相邻**的两个龙珠,放到目标队列的末尾(目标队列最开始是空的,且这两个龙珠的前后顺序不变),然后去除原龙珠队列的空隙。反复多次,直到原龙珠队列为空。可见,因为决策不一样导致目标队列顺序不一样。现在请求出所有方案中、目标队列字典序最大的方案。只需要给出目标队列即可。 例如,当原龙珠队列是 [1,3,2,4] 时,可以先取出 3 和 2,此时目标队列是 [3,2],原龙珠队列是 [1,4];再将剩下两个龙珠放入目标队列,得到目标队列是 [3,2,1,4]

输入输出格式

输入格式


第一行,一个整数 $n$。 接下来一行,每行 $n$ 个整数,表示原龙珠队列的编号。

输出格式


一行,$n$ 个整数。

输入输出样例

输入样例 #1

4 
3 1 4 2

输出样例 #1

4 2 3 1

输入样例 #2

6 
6 5 4 1 3 2

输出样例 #2

6 5 4 1 3 2

说明

对于 20% 的数据,$n\le10$。 对于 60% 的数据,$n\le10^3$。 对于 100% 的数据,$n\le10^5$,龙珠编号不超过 n。