## A Math Contest P3 - LIS Reconstruction

View as PDF

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

Author:
Problem type

Consider a permutation of the first positive integers, . Define as the length of the longest increasing subsequence of .

Given , find the lexicographically minimal possible permutation , or determine that no such permutation exists.

#### Input Specification

The first line contains an integer, .

The second line contains space-separated integers, .

#### Output Specification

If there is no sequence that can produce sequence , output ; otherwise, output one line containing positive integers, representing the lexicographically minimal permutation .

#### 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 is .
• The longest increasing subsequence of is .
• One of the longest increasing subsequences of is .

#### Sample Input 2

3
1 2 1

#### Sample Output 2

-1

#### Explanation for Sample Output 2

No possible permutation exists.