← 返回题目列表

Codeforces · 847/B

B. 准备合并排序

中文机器翻译题面 查看原题

Ivan 有一个由 n 个不同整数组成的数组。他决定按升序对所有元素重新排序。 Ivan 喜欢合并排序,因此他决定用一个或多个递增序列来表示他的数组,然后他计划将其合并到一个已排序的数组中。

Ivan 借助以下算法用递增序列表示他的数组。

虽然数组中至少有一个未使用的数字,但 Ivan 重复以下过程:

- 从左到右迭代数组;
- Ivan 仅查看当前迭代中未使用的数字;
- 如果当前数字是本次迭代中第一个未使用的数字,或者该数字大于当前迭代中先前未使用的数字,则 Ivan 将该数字标记为已使用并将其写下来。

例如,如果 Ivan 的数组看起来像 [1, 3, 2, 5, 4] 那么他将执行两次迭代。在第一次迭代中,Ivan 将使用并写入数字 [1, 3, 5],在第二次迭代中 - [2, 4]。

编写一个程序,帮助 Ivan 根据上述算法找到给定数组的一个或多个递增序列的表示。

输入

第一行包含一个整数 n (1 ≤ n ≤ 2·105) — Ivan 数组中的元素数量。

第二行包含一个由不同整数 a1, a2, ..., an (1 ≤ ai ≤ 109) 组成的序列 — Ivan 的数组。

输出

根据上述算法,以一个或多个递增序列的形式打印给定数组的表示。每个序列必须打印在新行上。

示例

输入 #1

5
1 3 2 5 4

输出 #1

1 3 5
2 4

输入 #2

4
4 3 2 1

输出 #2

4
3
2
1

输入 #3

4
10 30 50 101

输出 #3

10 30 50 101