Yet Another Contest 4 P2 - Alchemy 2

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

After decades of searching, you have discovered a special machine that allows you to transform different elements into each other!

The world consists of N elements labelled from 1 to N. Internally, the machine stores a sequence a_1, a_2, \dots, a_N such that 1 \le a_i \le N for all i. If you place element x into the machine, the machine will transform this into element a_x. Note that it is possible that a_x = x, in which case the machine does not do anything.

Let b_i be the number of distinct elements that you can obtain, starting with only a sample of element i and by using the machine zero or more times. You know the sequence b, but do not know the sequence a. Can you find any possible sequence a, or determine that you must have made a mistake and that no such sequence exists?


1 \le N \le 10^6

1 \le b_i \le N

Subtask 1 [30%]

For all z > 1 such that sequence b contains z, it is guaranteed that sequence b also contains z-1.

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains a single integer, N.

The second line contains N space-separated integers, b_1, b_2, \dots, b_N.

Output Specification

If there is no possible sequence a which would produce sequence b, output -1 on a single line.

Otherwise, output a_1, a_2, \dots, a_N, space-separated on a single line.

If there are multiple valid answers, you may output any of them.

Sample Input 1

2 2 3

Sample Output 1

2 1 1

Explanation for Sample Output 1

Starting with a sample of element 1 or element 2, we can obtain elements 1 and 2.

Starting with a sample of element 3, we can obtain elements 1, 2 and 3.

Note that \{2, 1, 2\} is another valid possibility for sequence a, and would also be accepted.

Sample Input 2

2 2 2

Sample Output 2


Explanation for Sample Output 2

It can be shown that no possible sequence a exists.


There are no comments at the moment.