Description

A monotonic stack is a common data structure. If you have not learned it before, you can refer to the Monotonic Stack Tutorial 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:

stack<int> stk;
int n = p.size();
vector<int> S;
for (int i = 0; i < n; i++) {
  while (!stk.empty() && p[i] <= p[stk.top()]) stk.pop();
  stk.push(i);
  S.push_back((int)stk.size());
}

Now you are given part of the sequence $S$. The parts that are not given may take any value. Please reconstruct a permutation $p$ that matches the given $S$. If there are multiple possibilities, output the lexicographically smallest one. It is guaranteed that a solution exists.

Input Format

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 Format

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

10
1 -1 2 3 -1 3 1 -1 2 3 

2 4 3 6 7 5 1 9 8 10

10
1 1 2 2 3 2 3 3 4 5 

2 1 5 4 6 3 8 7 9 10

Hint

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