Score : 1600 points
2^N players competed in a tournament. Each player has a unique ID number from 1 through 2^N. When two players play a match, the player with the smaller ID always wins.
This tournament was a little special, in which losers are not eliminated to fully rank all the players.
We will call such a tournament that involves 2^n players a full tournament of level n. In a full tournament of level n, the players are ranked as follows:
For example, the figure below shows how a full tournament of level 3 progresses when eight players are lined up in the order 3,4,8,6,2,1,7,5. The list of the players sorted by the final ranking will be 1,3,5,6,2,4,7,8.
Takahashi has a sheet of paper with the list of the players sorted by the final ranking in the tournament, but some of it blurred and became unreadable. You are given the information on the sheet as a sequence A of length N. When A_i is 1 or greater, it means that the i-th ranked player had the ID A_i. If A_i is 0, it means that the ID of the i-th ranked player is lost.
Determine whether there exists a valid order in the first phase of the tournament which is consistent with the sheet. If it exists, provide one such order.
Input is given from Standard Input in the following format:
N A_1 A_2 ... A_{2^N}
If there exists a valid order in the first phase of the tournament, print YES
first, then in the subsequent line, print the IDs of the players sorted by the final ranking, with spaces in between.
If there is no such order, print NO
instead.
3 0 3 0 6 0 0 0 8
YES 3 4 8 6 2 1 7 5
This is the same order as the one in the statement.
1 2 1
NO