Longest Increasing Subsequence

Time limit1sMemory limit256 MB

Summary

Given target LIS-ending lengths f_i, construct a permutation of 1..n whose longest increasing subsequence ending at position i has length exactly f_i.

Level: Medium7 of 10
Topics: Greedy, Sorting, Array, Implementation
Solved: No attempts yet

Problem

Given $f_1, f_2, \ldots, f_n$ , find a permutation $p_1, p_2, \ldots, p_n$ of the integers $1, 2, \ldots, n$ such that for each $i$ , the length of the longest strictly increasing subsequence ending with $p_i$ is $f_i$ .

Input

The first line contains an integer $n$ ( $1 \leq n \leq 10^5$ ).

The second line contains $n$ integers $f_1, f_2, \ldots, f_n$ ( $1 \leq f_i \leq n$ ). It is guaranteed that for the given input, at least one permutation $p_1, p_2, \ldots, p_n$ satisfying the condition exists.

Output

On the first line, print $n$ integers $p_1, p_2, \ldots, p_n$ . These numbers must form a permutation of $1, 2, \ldots, n$ . If there are several possible answers, print any one of them.

Examples2

Example 1
Input
```
7
1 1 1 1 1 1 1
```
Expected output
```
7 6 5 4 3 2 1
```
Example 2
Input
```
7
1 2 3 2 4 4 3
```
Expected output
```
1 3 5 2 7 6 4
```