311319: CF1970B2. Exact Neighbours (Medium)
Description
The only difference between this and the hard version is that $a_{1} = 0$.
After some recent attacks on Hogwarts Castle by the Death Eaters, the Order of the Phoenix has decided to station $n$ members in Hogsmead Village. The houses will be situated on a picturesque $n\times n$ square field. Each wizard will have their own house, and every house will belong to some wizard. Each house will take up the space of one square.
However, as you might know wizards are very superstitious. During the weekends, each wizard $i$ will want to visit the house that is exactly $a_{i}$ $(0 \leq a_{i} \leq n)$ away from their own house. The roads in the village are built horizontally and vertically, so the distance between points $(x_{i}, y_{i})$ and $(x_{j}, y_{j})$ on the $n\times n$ field is $ |x_{i} - x_{j}| + |y_{i} - y_{j}|$. The wizards know and trust each other, so one wizard can visit another wizard's house when the second wizard is away. The houses to be built will be big enough for all $n$ wizards to simultaneously visit any house.
Apart from that, each wizard is mandated to have a view of the Hogwarts Castle in the north and the Forbidden Forest in the south, so the house of no other wizard should block the view. In terms of the village, it means that in each column of the $n\times n$ field, there can be at most one house, i.e. if the $i$-th house has coordinates $(x_{i}, y_{i})$, then $x_{i} \neq x_{j}$ for all $i \neq j$.
The Order of the Phoenix doesn't yet know if it is possible to place $n$ houses in such a way that will satisfy the visit and view requirements of all $n$ wizards, so they are asking for your help in designing such a plan.
If it is possible to have a correct placement, where for the $i$-th wizard there is a house that is $a_{i}$ away from it and the house of the $i$-th wizard is the only house in their column, output YES, the position of houses for each wizard, and to the house of which wizard should each wizard go during the weekends.
If it is impossible to have a correct placement, output NO.
InputThe first line contains $n$ ($2 \leq n \leq 2\cdot 10^{5}$), the number of houses to be built.
The second line contains $n$ integers $a_{1}, \ldots, a_{n}$ $(0 \leq a_{i} \leq n)$, $a_{1} = 0$.
OutputIf there exists such a placement, output YES on the first line; otherwise, output NO.
If the answer is YES, output $n + 1$ more lines describing the placement.
The next $n$ lines should contain the positions of the houses $1 \leq x_{i}, y_{i} \leq n$ for each wizard.
The $i$-th element of the last line should contain the index of the wizard, the house of which is exactly $a_{i}$ away from the house of the $i$-th wizard. If there are multiple such wizards, you can output any.
If there are multiple house placement configurations, you can output any.
ExamplesInput4 0 4 2 4Output
YES 4 4 1 3 2 4 3 1 1 1 1 3Input
4 0 1 3 1Output
YES 1 1 2 1 4 1 3 1 1 1 1 3Note
For the sample, the house of the 1st wizard is located at $(4, 4)$, of the 2nd at $(1, 3)$, of the 3rd at $(2, 4)$, of the 4th at $(3, 1)$.
The distance from the house of the 1st wizard to the house of the 1st wizard is $|4 - 4| + |4 - 4| = 0$.
The distance from the house of the 2nd wizard to the house of the 1st wizard is $|1 - 4| + |3 - 4| = 4$.
The distance from the house of the 3rd wizard to the house of the 1st wizard is $|2 - 4| + |4 - 4| = 2$.
The distance from the house of the 4th wizard to the house of the 3rd wizard is $|3 - 2| + |1 - 4| = 4$.
The view and the distance conditions are satisfied for all houses, so the placement is correct.
Output
这个题目与困难版本的不同之处仅在于 $ a_{1} = 0 $。霍格沃茨城堡最近遭受了食死徒的袭击，凤凰社决定在霍格莫德村部署 $ n $ 名成员。房屋将位于一个美丽的 $ n \times n $ 方形田野上。每个巫师都将有自己的房子，每所房子都将属于某个巫师。每所房子将占据一个方格的空间。
然而，正如你所知，巫师们非常迷信。在周末，每个巫师 $ i $ 都会想去拜访离他们自己的房子正好 $ a_{i} $ ($ 0 \leq a_{i} \leq n $) 远的房子。村里的道路是水平垂直建造的，所以 $ n \times n $ 田野上点 $ (x_{i}, y_{i}) $ 和 $ (x_{j}, y_{j}) $ 之间的距离是 $ |x_{i} - x_{j}| + |y_{i} - y_{j}| $。巫师们相互了解和信任，所以当一个巫师不在时，另一个巫师可以拜访他的房子。要建造的房子将足够大，以允许所有 $ n $ 个巫师同时访问任何一所房子。
除此之外，每个巫师都必须看到北边的霍格沃茨城堡和南边的禁林，所以其他巫师的房子不应该挡住视线。在村子的意义上，这意味着在 $ n \times n $ 田野的每一列中最多只能有一个房子，即如果第 $ i $ 所房子的坐标是 $ (x_{i}, y_{i}) $，那么 $ x_{i} \neq x_{j} $ 对于所有 $ i \neq j $。
凤凰社还不知道是否有可能以这种方式放置 $ n $ 所房子，以满足所有 $ n $ 个巫师的访问和视线要求，所以他们请求你帮助设计这样的计划。
如果存在正确的放置方式，其中对于第 $ i $ 个巫师，有一个离他 $ a_{i} $ 远的房子，并且第 $ i $ 个巫师的房子是它列中唯一的房子，输出 `YES`，每个巫师房子的位置，以及每个巫师在周末应该去哪个巫师的房子。
如果不可能有正确的放置，输出 `NO`。
输入数据格式：
第一行包含 $ n $ ($ 2 \leq n \leq 2 \cdot 10^{5} $)，要建造的房子数量。
第二行包含 $ n $ 个整数 $ a_{1}, \ldots, a_{n} $ ($ 0 \leq a_{i} \leq n $)，$ a_{1} = 0 $。
输出数据格式：
如果存在这样的放置，第一行输出 `YES`；否则，输出 `NO`。
如果答案是 `YES`，输出 $ n + 1 $ 更多行描述放置。
接下来的 $ n $ 行应该包含每个巫师房子的位置 $ 1 \leq x_{i}, y_{i} \leq n $。
最后一行的第 $ i $ 个元素应该包含离第 $ i $ 个巫师房子正好 $ a_{i} $ 远的巫师的房子的索引。如果有多个这样的巫师，你可以输出任何一个。
如果有多个房屋放置配置，你可以输出任何一个。题目大意： 这个题目与困难版本的不同之处仅在于 $ a_{1} = 0 $。霍格沃茨城堡最近遭受了食死徒的袭击，凤凰社决定在霍格莫德村部署 $ n $ 名成员。房屋将位于一个美丽的 $ n \times n $ 方形田野上。每个巫师都将有自己的房子，每所房子都将属于某个巫师。每所房子将占据一个方格的空间。 然而，正如你所知，巫师们非常迷信。在周末，每个巫师 $ i $ 都会想去拜访离他们自己的房子正好 $ a_{i} $ ($ 0 \leq a_{i} \leq n $) 远的房子。村里的道路是水平垂直建造的，所以 $ n \times n $ 田野上点 $ (x_{i}, y_{i}) $ 和 $ (x_{j}, y_{j}) $ 之间的距离是 $ |x_{i} - x_{j}| + |y_{i} - y_{j}| $。巫师们相互了解和信任，所以当一个巫师不在时，另一个巫师可以拜访他的房子。要建造的房子将足够大，以允许所有 $ n $ 个巫师同时访问任何一所房子。 除此之外，每个巫师都必须看到北边的霍格沃茨城堡和南边的禁林，所以其他巫师的房子不应该挡住视线。在村子的意义上，这意味着在 $ n \times n $ 田野的每一列中最多只能有一个房子，即如果第 $ i $ 所房子的坐标是 $ (x_{i}, y_{i}) $，那么 $ x_{i} \neq x_{j} $ 对于所有 $ i \neq j $。 凤凰社还不知道是否有可能以这种方式放置 $ n $ 所房子，以满足所有 $ n $ 个巫师的访问和视线要求，所以他们请求你帮助设计这样的计划。 如果存在正确的放置方式，其中对于第 $ i $ 个巫师，有一个离他 $ a_{i} $ 远的房子，并且第 $ i $ 个巫师的房子是它列中唯一的房子，输出 `YES`，每个巫师房子的位置，以及每个巫师在周末应该去哪个巫师的房子。 如果不可能有正确的放置，输出 `NO`。 输入数据格式： 第一行包含 $ n $ ($ 2 \leq n \leq 2 \cdot 10^{5} $)，要建造的房子数量。 第二行包含 $ n $ 个整数 $ a_{1}, \ldots, a_{n} $ ($ 0 \leq a_{i} \leq n $)，$ a_{1} = 0 $。 输出数据格式： 如果存在这样的放置，第一行输出 `YES`；否则，输出 `NO`。 如果答案是 `YES`，输出 $ n + 1 $ 更多行描述放置。 接下来的 $ n $ 行应该包含每个巫师房子的位置 $ 1 \leq x_{i}, y_{i} \leq n $。 最后一行的第 $ i $ 个元素应该包含离第 $ i $ 个巫师房子正好 $ a_{i} $ 远的巫师的房子的索引。如果有多个这样的巫师，你可以输出任何一个。 如果有多个房屋放置配置，你可以输出任何一个。