P6035 Ryoku 的逆序对

Ryoku 并不知道这题的背景是什么。

Ryoku 有一个正整数 $\{1,2,\cdots,n\}$ 的排列 $A = \{a_i\}$。 她告诉你一个序列 $B = \{b_i\}$，表示对于每个数 $a_i$，对于所有 $j>i$ 有 $b_i$ 个数可以与 $a_i$ 组成逆序对（逆序对的定义是：满足 $i>j$ 且 $a_i < a_j$ 的一组 $(a_i, a_j)$ 称作一对逆序对）。 不幸的是，Ryoku 给你的序列 $B$ 有一些位置污损了，你想知道有多少个可能的排列 $A$ 能符合条件。 请你输出答案并构造一个**字典序最小**的排列 $A$（对于排列 $A = \{a_i\},\ A' = \{a'_i\}$ 若存在某个位置 $i$，使得 $\forall j < i, a_j = a'_j$ 且 $a_i < a'_i$，则 $A$ 的字典序小于 $A'$）。

无

无

**【样例 1 说明】** 对于 $5$，存在逆序对 $(5,2),(5,3),(5,4)$ 共三对。 **【样例 2 说明】** 符合条件的排列有：$\{1, 5, 4, 2, 3\}, \{1, 5, 3, 2, 4\}, \{1, 5, 2, 3, 4\}$。共三种，其中字典序最小的为 $\{1, 5, 2, 3, 4\}$。 --- **【数据规模与约定】** 对于 $10\%$ 的数据，$b_i \neq -1$。 对于另外 $10\%$ 的数据，$n \le 10$。 对于另外 $10\%$ 的数据，$b_i = -1$。 对于另外 $30\%$ 的数据，$n \le 10^3$。 对于另外 $30\%$ 的数据，$n \le 10^5$。 对于 $100\%$ 的数据，$0< n \le 10^6$，$-1 \le b_i \le n$。