P6198 [EER1] Monotonic Stack

A monotonic stack is a common data structure. If you have not learned it before, you can refer to the [Monotonic Stack Tutorial](https://www.luogu.com.cn/problemnew/solution/P5788) to help understand the problem. There is a **permutation** $p_0, p_1, \cdots, p_{n-1}$ of length $n$. Using this permutation, we generate a sequence $S$ of length $n$, where $S_i$ denotes the size of the increasing monotonic stack built from $p_0, p_1, \cdots, p_i$. In other words, the sequence $S$ is generated by the following code: ```cpp stack stk; int n = p.size(); vector S; for (int i = 0; i < n; i++) { while (!stk.empty() && p[i]

The first line contains an integer $n$, the length of the permutation. The next line contains $n$ integers, representing the sequence $S$. Some entries are $-1$, meaning they can take any value.

Output one line with $n$ integers, a permutation.

Explanation for Sample #1: The output for Sample $1$ corresponds to the sequence $S$ as 1 2 2 3 4 3 1 2 2 3, which matches the input. It can be proven that this is the lexicographically smallest permutation that can match the input. For $100\%$ of the testdata, $1 \leq n \leq 10^6$. This problem has $5$ subtasks, and the limits are as follows: Subtask $1$ ($5$ points): It is guaranteed that $1 \leq n \leq 10$. Subtask $2$ ($10$ points): It is guaranteed that there is no $-1$ in the given $S$. Subtask $3$ ($20$ points): It is guaranteed that $1 \leq n \leq 300$. Subtask $4$ ($20$ points): It is guaranteed that $1 \leq n \leq 3000$. Subtask $5$ ($45$ points): No additional constraints. Translated by ChatGPT 5