Permutations#5304
Sasha and Fedya are playing an interesting game. They have dice, each labeled with a distinct integer from to . The players draw cells in a row on a sheet of paper and play according to the following rules.
First, the first player places some of the dice into cells. Then, the second player places the remaining dice into the empty cells. After that, the first player makes the following actions: he checks the number written on the last die (let this number be ) and then reverses the order of the last dice. The first player repeats these actions until the last die becomes the die with number .
For example, let the boys have five dice. If the first player places the second and third dice in the third and fifth positions, so the arrangement looks like «..3.2», the second player can complete the arrangement as «41352». In this case, the first player will need to make five moves: «41325», «52314», «54132», «54123», «54321», after which the game ends.
Sasha made the first move. Help Fedya arrange the dice so that Sasha will have to make the maximum possible number of moves.
The first line contains the number (1 \leq n \leq 25). The next numbers represent the arrangement of dice after Sasha's move. A means the cell is empty, and a number from to means the die with this number is placed in that cell. There are no more than zeros in the input.
On the first line, print the maximum number of moves Sasha will need to make. On the second line, print numbers from to , where the -th number is the die in the -th cell after Fedya's move. If there are multiple optimal solutions, any of them may be printed.
Example 1