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?
Constraints
Subtask 1 [30%]
For all such that sequence
contains
, it is guaranteed that sequence
also contains
.
Subtask 2 [70%]
No additional constraints.
Input Specification
The first line contains a single integer, .
The second line contains space-separated integers,
.
Output Specification
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
-1
Explanation for Sample Output 2
It can be shown that no possible sequence exists.
Comments