A Math Contest P3 - LIS Reconstruction

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Consider a permutation of the first N positive integers, p_1, p_2, \dots, p_N. Define a_i as the length of the longest increasing subsequence of p_1, p_2, \dots, p_i.

Given a_1, a_2, \dots, a_n, find the lexicographically minimal possible permutation p_1, p_2, \dots, p_N, or determine that no such permutation exists.

Constraints

1 \le N \le 2 \times 10^5

1 \le a_i \le N

Input Specification

The first line contains an integer, N.

The second line contains N space-separated integers, a_1, a_2, \dots, a_N.

Output Specification

If there is no sequence p that can produce sequence a, output -1; otherwise, output one line containing N positive integers, representing the lexicographically minimal permutation p_1, p_2, \dots, p_N.

Sample Input 1

3
1 2 2

Sample Output 1

1 3 2

Explanation for Sample Output 1

Note that

  • The longest increasing subsequence of p_1 is 1.
  • The longest increasing subsequence of p_1, p_2 is 1, 3.
  • One of the longest increasing subsequences of p_1, p_2, p_3 is 1, 2.

Sample Input 2

3
1 2 1

Sample Output 2

-1

Explanation for Sample Output 2

No possible permutation p exists.


Comments

There are no comments at the moment.