After decades of searching, you have discovered a special machine that allows you to transform different elements into each other!
The world consists of elements labelled from to . Internally, the machine stores a sequence such that for all . If you place element into the machine, the machine will transform this into element . Note that it is possible that , in which case the machine does not do anything.
Let be the number of distinct elements that you can obtain, starting with only a sample of element and by using the machine zero or more times. You know the sequence , but do not know the sequence . Can you find any possible sequence , or determine that you must have made a mistake and that no such sequence exists?
Subtask 1 [30%]
For all such that sequence contains , it is guaranteed that sequence also contains .
Subtask 2 [70%]
No additional constraints.
The first line contains a single integer, .
The second line contains space-separated integers, .
If there is no possible sequence which would produce sequence , output on a single line.
Otherwise, output , space-separated on a single line.
If there are multiple valid answers, you may output any of them.
Sample Input 1
3 2 2 3
Sample Output 1
2 1 1
Explanation for Sample Output 1
Starting with a sample of element or element , we can obtain elements and .
Starting with a sample of element , we can obtain elements , and .
Note that is another valid possibility for sequence , and would also be accepted.
Sample Input 2
3 2 2 2
Sample Output 2
Explanation for Sample Output 2
It can be shown that no possible sequence exists.