CF1517C.Fillomino 2

Fillomino is a classic logic puzzle. (You do not need to know Fillomino in order to solve this problem.) In one classroom in Yunqi town, some volunteers are playing a board game variant of it:

Consider an $n$ by $n$ chessboard. Its rows are numbered from $1$ to $n$ from the top to the bottom. Its columns are numbered from $1$ to $n$ from the left to the right. A cell on an intersection of $x$-th row and $y$-th column is denoted $(x, y)$. The main diagonal of the chessboard is cells $(x, x)$ for all $1 \le x \le n$.

A permutation of ${1, 2, 3, \dots, n}$ is written on the main diagonal of the chessboard. There is exactly one number written on each of the cells. The problem is to partition the cells under and on the main diagonal (there are exactly $1+2+ \ldots +n$ such cells) into $n$ connected regions satisfying the following constraints:

1. Every region should be connected. That means that we can move from any cell of a region to any other cell of the same region visiting only cells of the same region and moving from a cell to an adjacent cell.
2. The $x$-th region should contain cell on the main diagonal with number $x$ for all $1\le x\le n$.
3. The number of cells that belong to the $x$-th region should be equal to $x$ for all $1\le x\le n$.
4. Each cell under and on the main diagonal should belong to exactly one region.

Fillomino 是一道经典的逻辑谜题。（求解本题无需了解 Fillomino。）在云栖镇的一间教室中，一些志愿者正在玩它的一个棋盘游戏变种：

考虑一个 $n \times 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. 第 $x$ 个区域必须包含主对角线上数值为 $x$ 的格子（对所有 $1\le x\le n$ 成立）。
3. 第 $x$ 个区域所含格子数必须恰好为 $x$（对所有 $1\le x\le n$ 成立）。
4. 主对角线及其下方的每个格子必须恰好属于一个区域。

The first line contains a single integer $n$ ($1\le n \le 500$) denoting the size of the chessboard.

The second line contains $n$ integers $p_1$, $p_2$, ..., $p_n$. $p_i$ is the number written on cell $(i, i)$. It is guaranteed that each integer from ${1, \ldots, n}$ appears exactly once in $p_1$, ..., $p_n$.

第一行包含一个整数 $n$（$1\le n \le 500$），表示棋盘的大小。

第二行包含 $n$ 个整数 $p_1$, $p_2$, ..., $p_n$。其中 $p_i$ 表示格子 $(i, i)$ 上所写的数字。保证 $p_1$, ..., $p_n$ 恰好构成集合 $\{1, \ldots, n\}$ 的一个排列。

If no solution exists, output $-1$.

Otherwise, output $n$ lines. The $i$-th line should contain $i$ numbers. The $j$-th number on the $i$-th line should be $x$ if cell $(i, j)$ belongs to the the region with $x$ cells.

如果不存在解，则输出 $-1$。

否则，输出 $n$ 行。第 $i$ 行应包含 $i$ 个数字。第 $i$ 行的第 $j$ 个数字应为 $x$，其中 $x$ 是包含格子 $(i, j)$ 的区域所含的格子总数。

The solutions to the examples are illustrated in the following pictures:

示例的解法如下图所示：