有 $N$ 块石头排成一行。所有石头的重量均为 $1$ 到 $N$ 之间的不同整数。任务是将这些石头按重量从轻到重排列。

大象 Jumbo 在一次操作中，可以从行中取出任意数量的石头，并将它们放回行的最前面，且不改变它们的相对顺序。

例如，考虑一行 5 块石头，重量为 $[3, 1, 5, 4, 2]$。如果 Jumbo 选择第 2 块和第 5 块石头，他可以在一次操作中将该行变为 $[1, 2, 3, 5, 4]$。

求 Jumbo 将给定的石头行按重量排序所需的最少操作次数，并打印出一种可能的最佳排序方式。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 10^5$)。第二行包含 $N$ 个整数，其中第 $i$ 个整数表示第 $i$ 块石头的重量。所有重量均为 $1$ 到 $N$ 之间的不同整数。

输出格式

第一行应包含整数 $M$ —— 最少操作次数。接下来的 $M + 1$ 行，每行应包含 $N$ 个数字：第一行表示初始状态，其余各行表示每次操作后的状态。

样例

样例输入 1

5
3 1 5 4 2

样例输出 1

2
3 1 5 4 2
1 5 2 3 4
1 2 3 4 5

样例输入 2

4
2 1 3 4

样例输出 2

1
2 1 3 4
1 2 3 4