Permutation Recovery from Monotonic Stack

Consider a permutation (p_0, p_1, \dots, p_{n-1}) of the integers (1,2,\dots,n). Using this permutation, a sequence (S) of length (n) is generated by simulating the following procedure (the indices are (0)-based):

[ \texttt{stack stk;}\ for (int i = 0; i < n; i++) {\   while (!stk.empty() && p[i] \le p[stk.top()]) stk.pop();\   stk.push(i);\   S_i = \text{(current size of stk)}; } ]

In other words, for each (i), (S_i) is the size of the increasing (monotonic) stack obtained when processing (p_0, p_1, \dots, p_i).

You are given a partial sequence (S) of length (n). Some entries of (S) are provided while the others are missing (represented by (-1)); you may assume that the missing entries can be any integer (as they are not constrained). Your task is to recover a permutation (p) such that when the above procedure is applied, for every (i) for which (S_i) is given (i.e. not (-1)) the computed stack‐size equals (S_i). If there are multiple solutions, output the lexicographically smallest permutation.

It is guaranteed that at least one solution exists.

Note: A permutation of (1,2,\dots,n) is a reordering of these (n) numbers. Also, by simulation it is clear that (S_0 = 1) always.

inputFormat

The input consists of two lines.

The first line contains an integer (n) (with a small constraint, e.g. (1 \le n \le 8)).

The second line contains (n) space‐separated integers (S_0, S_1, \dots, S_{n-1}). Missing values are indicated by (-1). For every index (i) where (S_i \neq -1) the value is guaranteed to be the intended stack size after processing (p_0,\dots,p_i) in the simulation described above.

outputFormat

Output the lexicographically smallest permutation (p_0, p_1, \dots, p_{n-1}) (space–separated) that produces a sequence (S) (via the procedure given in the problem statement) matching all the provided values.

sample

3
1 1 2

2 1 3