Fillomino 是一款经典的逻辑谜题。 (你不需要认识菲洛米诺就能解决这个问题。)在云栖镇的一间教室里,一些志愿者正在玩它的一种棋盘游戏:
考虑一个由 $$$n$$$ 组成的 $$$n$$$ 棋盘。其行从上到下编号为 $$$1$$$ 到 $$$n$$$。其列从左到右编号为 $$$1$$$ 到 $$$n$$$。 $$$x$$$ 行和 $$$y$$$ 列交叉处的单元格表示为 $$$(x, y)$$$。棋盘的主对角线是所有 $$$1 \le x \le n$$$ 的单元格 $$$(x, x)$$$。
$$$\{1, 2, 3, \dots, n\}$$$ 的排列写在棋盘的主对角线上。每个单元格上都写有一个数字。问题是将主对角线下方和主对角线上的单元格(正好有 $$$1+2+ \ldots +n$$$ 这样的单元格)划分为满足以下约束的 $$$n$$$ 连接区域:
1. 每个区域都应该连接。这意味着我们可以从一个区域的任何单元格移动到同一区域的任何其他单元格,仅访问同一区域的单元格并从一个单元格移动到相邻的单元格。
2. 对于所有 $$$1\le x\le n$$$,第 $$$x$$$ 区域应在主对角线上包含编号为 $$$x$$$ 的单元格。
3. 对于所有 $$$1\le x\le n$$$,属于第 $$$x$$$ 区域的单元格数量应等于 $$$x$$$。
4. 主对角线下方和主对角线上的每个单元格都应该属于一个区域。
输入
第一行包含一个整数 $$$n$$$ ($$$1\le n \le 500$$$) 表示棋盘的大小。
第二行包含 $$$n$$$ 整数 $$$p_1$$$、$$$p_2$$$、...、$$$p_n$$$。 $$$p_i$$$ 是写在单元格 $$$(i, i)$$$ 上的数字。保证 $$$\{1, \ldots, n\}$$$ 中的每个整数在 $$$p_1$$$, ..., $$$p_n$$$ 中恰好出现一次。
输出
如果不存在解,则输出$$$-1$$$。
否则,输出 $$$n$$$ 行。第 $$$i$$$ 行应包含 $$$i$$$ 数字。如果单元格 $$$(i, j)$$$ 属于包含 $$$x$$$ 单元格的区域,则第 $$$i$$$ 行上的第 $$$j$$$ 数字应为 $$$x$$$。
示例
输入 #1
3 2 3 1
输出 #1
2 2 3 3 3 1
输入 #2
5 1 2 3 4 5
输出 #2
1 2 2 3 3 3 4 4 4 4 5 5 5 5 5
注意
示例的解决方案如下图所示: