题目描述

GrandPa（简称 GP）年轻时非常喜欢算法竞赛。他参加过 $N$ 场重要比赛，并且每场都获得第一名、赢得一个奖杯。为了方便区分，他给这些奖杯分别编号为 $1$ 到 $N$，且任意两个不同奖杯的编号不同。

现在，这 $N$ 个奖杯从左到右摆在书架 $A$ 上。第 $i$ 个奖杯的编号为 $P_i$。

GP 很快要被孙辈们拜访，他想把奖杯摆得尽可能“震撼”。他会把书架 $A$ 上的奖杯移动到另一个初始为空的书架 $B$ 上。每次操作如下：

1. 从书架 $A$ 中选择最左边或最右边的一个奖杯；
2. 将这个奖杯放到书架 $B$ 的最左边或最右边。如果 $B$ 为空，则放在哪里都等价。

一直操作到书架 $A$ 为空、所有奖杯都被移动到书架 $B$ 上。

设最终书架 $B$ 上从左到右的编号序列为 $Q_1,Q_2,\ldots,Q_N$。GP 希望通过合理操作，使得序列 $Q$ 在所有可能得到的序列中字典序最大。

请输出这个字典序最大的序列 $Q$。

输入格式

第一行一个整数 $N$。

第二行 $N$ 个整数：

表示初始书架 $A$ 上从左到右的奖杯编号。

输出格式

输出一行 $N$ 个整数：

表示能够得到的字典序最大的最终序列。

约束与说明

• $1\le N\le 100000$

• $1\le P_i\le N$

• 若 $i\ne j$，则 $P_i\ne P_j$

• 对于两个长度同为 $K$ 的序列 $A,B$，若存在位置 $p$，满足：

  • $A_p>B_p$；
  • 对所有 $1\le i<p$，都有 $A_i=B_i$；

  则称 $A$ 的字典序大于 $B$。

子任务

样例 1

输入

4
3 2 4 1

输出

4 3 2 1

样例 2

输入

6
1 4 2 6 5 3

输出

6 5 4 3 1 2

样例 3

输入

10
9 7 8 5 1 4 2 3 6 10

输出

10 9 7 8 6 5 3 2 4 1

样例解释

样例 1 中，可以按如下方式移动：

样例 2 中，可以按如下方式移动：