#P1970B1. Exact Neighbours (Easy)

Exact Neighbours (Easy)

Description

The only difference between this and the hard version is that all aia_{i} are even.

After some recent attacks on Hogwarts Castle by the Death Eaters, the Order of the Phoenix has decided to station nn members in Hogsmead Village. The houses will be situated on a picturesque n×nn\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 ii will want to visit the house that is exactly aia_{i} (0ain)(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 (xi,yi)(x_{i}, y_{i}) and (xj,yj)(x_{j}, y_{j}) on the n×nn\times n field is xixj+yiyj |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 nn 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×nn\times n field, there can be at most one house, i.e. if the ii-th house has coordinates (xi,yi)(x_{i}, y_{i}), then xixjx_{i} \neq x_{j} for all iji \neq j.

The Order of the Phoenix doesn't yet know if it is possible to place nn houses in such a way that will satisfy the visit and view requirements of all nn 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 ii-th wizard there is a house that is aia_{i} away from it and the house of the ii-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.

The first line contains nn (2n21052 \leq n \leq 2\cdot 10^{5}), the number of houses to be built.

The second line contains nn integers a1,,ana_{1}, \ldots, a_{n} (0ain)(0 \leq a_{i} \leq n). All aia_{i} are even.

If there exists such a placement, output YES on the first line; otherwise, output NO.

If the answer is YES, output n+1n + 1 more lines describing the placement.

The next nn lines should contain the positions of the houses 1xi,yin1 \leq x_{i}, y_{i} \leq n for each wizard.

The ii-th element of the last line should contain the index of the wizard, the house of which is exactly aia_{i} away from the house of the ii-th wizard. If there are multiple such wizards, you can output any.

If there are multiple house placement configurations, you can output any.

Input

The first line contains nn (2n21052 \leq n \leq 2\cdot 10^{5}), the number of houses to be built.

The second line contains nn integers a1,,ana_{1}, \ldots, a_{n} (0ain)(0 \leq a_{i} \leq n). All aia_{i} are even.

Output

If there exists such a placement, output YES on the first line; otherwise, output NO.

If the answer is YES, output n+1n + 1 more lines describing the placement.

The next nn lines should contain the positions of the houses 1xi,yin1 \leq x_{i}, y_{i} \leq n for each wizard.

The ii-th element of the last line should contain the index of the wizard, the house of which is exactly aia_{i} away from the house of the ii-th wizard. If there are multiple such wizards, you can output any.

If there are multiple house placement configurations, you can output any.

样例输入 1

4
0 4 2 4

样例输出 1

YES
4 4
1 3
2 4
3 1
1 1 1 3

Note

For the sample, the house of the 1st wizard is located at (4,4)(4, 4), of the 2nd at (1,3)(1, 3), of the 3rd at (2,4)(2, 4), of the 4th at (3,1)(3, 1).

The distance from the house of the 1st wizard to the house of the 1st wizard is 44+44=0|4 - 4| + |4 - 4| = 0.

The distance from the house of the 2nd wizard to the house of the 1st wizard is 14+34=4|1 - 4| + |3 - 4| = 4.

The distance from the house of the 3rd wizard to the house of the 1st wizard is 24+44=2|2 - 4| + |4 - 4| = 2.

The distance from the house of the 4th wizard to the house of the 3rd wizard is 32+14=4|3 - 2| + |1 - 4| = 4.

The view and the distance conditions are satisfied for all houses, so the placement is correct.