题目描述

单调栈是一种常见的数据结构，如果你之前没有了解过，可以参考 单调栈教程 帮助理解题意。

有一个长度为 $n$ 的排列 $p_0, p_1, \cdots, p_{n-1}$，通过这个排列生成了一个长度为 $n$ 的序列 $S$，其中 $S_i$ 表示由 $p_0, p_1, \cdots, p_i$ 组成的递增单调栈的大小。

换一种说法，序列 $S$ 是由如下代码生成的：

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());
}

现在给你序列 $S$ 的一部分，没有给出的部分可以取任意值。请你根据给出的 $S$ 复原出排列 $p$。如果有多种可能，输出字典序最小的。保证一定有解。

输入格式

第一行一个整数 $n$。表示排列的长度。

接下来一行 $n$ 个整数，表示序列 $S$。其中部分项为 $-1$，表示可以取任意值。

输出格式

一行 $n$ 个整数，一个排列。

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

提示

样例 #1 解释：样例 $1$ 的输出对应的 $S$ 序列为 1 2 2 3 4 3 1 2 2 3，可以匹配输入。可以证明这是字典序最小的可以匹配输入的排列。

对于 $100\%$ 的数据，满足 $1 \leq n \leq 10^6$。

本题共有 $5$ 个子任务，每个子任务的限制如下：

子任务 $1$ ($5$ 分)：保证 $1 \leq n \leq 10$。

子任务 $2$ ($10$ 分)：保证给出的 $S$ 中没有 $-1$。

子任务 $3$ ($20$ 分)：保证 $1 \leq n \leq 300$。

子任务 $4$ ($20$ 分)：保证 $1 \leq n \leq 3000$。

子任务 $5$ ($45$ 分)：无特殊限制。