当前没有测试数据。

【例题3】龙珠游戏

题目描述

"龙珠"是一款益智小游戏。游戏中有$n$（$n$是偶数）个编号，龙珠按照给定的顺序排成一个队列，每个龙珠上面都有一个编号。每次操作时，选择并取出龙珠队列中相邻的两个龙珠，放到目标队列的末尾（目标队列最开始是空的，且这两个龙珠的前后顺序不变），然后去除原龙珠队列的空隙。反复多次，直到原龙珠队列为空。显然决策不一样会导致目标队列龙珠顺序不一样。现在请求出所有方案中、目标队列字典序最大的方案。只需要给出目标队列即可。

例如，当原龙珠队列是$[1,3,2,4]$时，可以先取出$3$和$2$，此时目标队列是$[3,2]$，原龙珠队列是$[1,4]$；再将剩下两个龙珠放入目标队列，得到目标队列是$[3,2,1,4]$。

输入格式

第一行：一个整数$n$。

第二行：$n$个整数，表示原龙珠队列的编号。

输出格式

一行，$n$个整数，表示字典序最大的目标队列。

数据范围与提示

• 对于$20\%$的数据，$n \leq 10$；
• 对于$60\%$的数据，$n \leq 10^3$；
• 对于$100\%$的数据，$n \leq 10^5$，龙珠编号不超过$n$。

样例

4 
3 1 4 2

4 2 3 1

6 
6 5 4 1 3 2

6 5 4 1 3 2