Description

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 $i<j$ and $a_i>a_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'$).

Input Format

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.

Output Format

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.

5
0 3 0 0 0

1
1 5 2 3 4

5
0 3 -1 0 0

3
1 5 2 3 4

5
0 3 -1 0 1

0

Hint

[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