P6035 Ryoku's Inversion Pairs

Ryoku does not know what the background of this problem is.

Ryoku has a permutation $A = \{a_i\}$ of the positive integers $\{1,2,\cdots,n\}$. She tells you a sequence $B = \{b_i\}$. For each number $a_i$, among all $j>i$, there are exactly $b_i$ numbers that can form an inversion pair with $a_i$ (an inversion pair is defined as follows: a pair $(a_i, a_j)$ that satisfies $ia_j$ is called an inversion pair). Unfortunately, some positions in the sequence $B$ Ryoku gave you are damaged. You want to know how many possible permutations $A$ can satisfy the condition. Please output the answer and construct the **lexicographically smallest** permutation $A$ (for permutations $A = \{a_i\}$ and $A' = \{a'_i\}$, if there exists a position $i$ such that $\forall j < i, a_j = a'_j$ and $a_i < a'_i$, then $A$ is lexicographically smaller than $A'$).

The input contains two lines. The first line contains an integer $n$. The second line contains $n$ integers, which form the sequence $B$. If $b_i = -1$, it means this position is damaged.

The output contains two lines. The first line contains an integer, the number of possible permutations $A$, taken modulo $10^9 + 7$. The second line contains $n$ integers, the lexicographically smallest permutation that satisfies the condition. If the answer in the first line is $0$, then the second line does not need to be output.

**[Sample 1 Explanation]** For $5$, there are inversion pairs $(5,2),(5,3),(5,4)$, a total of three pairs. **[Sample 2 Explanation]** The permutations that satisfy the condition are: $\{1, 5, 4, 2, 3\}, \{1, 5, 3, 2, 4\}, \{1, 5, 2, 3, 4\}$. There are three in total, and the lexicographically smallest is $\{1, 5, 2, 3, 4\}$. --- **[Constraints]** For $10\%$ of the testdata, $b_i \neq -1$. For another $10\%$ of the testdata, $n \le 10$. For another $10\%$ of the testdata, $b_i = -1$. For another $30\%$ of the testdata, $n \le 10^3$. For another $30\%$ of the testdata, $n \le 10^5$. For $100\%$ of the testdata, $0< n \le 10^6$, $-1 \le b_i \le n$. Translated by ChatGPT 5