Permutation Reconstruction from Partial Inversion Sequence

Ryoku has a permutation \(A = \{a_1,a_2,\dots,a_n\}\) of the positive integers \(\{1,2,\dots,n\}\). She also gives you a sequence \(B = \{b_1,b_2,\dots,b_n\}\) where for each element \(a_i\) the number \(b_i\) represents the count of inversion pairs that \(a_i\) forms with some elements to its right. Here an inversion pair is defined as a pair \((a_i,a_j)\) such that \(i a_j\) (this is equivalent to the definition: there exists a pair \((a_i,a_j)\) with indices satisfying \(i > j\) and \(a_i < a_j\)).

Recall that for any permutation of \(n\) numbers, the corresponding inversion sequence \(B = (b_1, b_2, \dots, b_n)\) must satisfy \(0 \le b_i \le n-i\) for \(1 \le i \le n\) (here we use 1-indexing). In our problem, some positions of the sequence \(B\) are damaged and are given as \(-1\). In other words, if \(b_i = -1\), then the actual value at that position is unknown and can be any integer in the range \([0, n-i]\).

Your task is twofold:

1. Calculate the number of possible permutations \(A\) whose inversion sequence \(B' = (b'_1, b'_2, \dots, b'_n)\) agrees with the given \(B\) at all positions where \(B\) is not damaged. For every damaged position \(i\) (i.e. \(b_i = -1\)), you may choose any value in \([0, n-i]\). Thus, the number of choices for position \(i\) is \(n-i+1\) if it is damaged. (Assume that the given values at non-damaged positions are valid.)
2. Among all valid permutations, construct the lexicographically smallest permutation \(A\). A permutation \(A = (a_1, a_2, \dots, a_n)\) is lexicographically smaller than another permutation \(A' = (a'_1, a'_2, \dots, a'_n)\) if there exists an index \(i\) such that \(a_1=a'_1,\,a_2=a'_2,\,\dots, a_{i-1}=a'_{i-1}\) and \(a_i < a'_i\).

Reconstruction Note: There is a well-known bijection between inversion sequences and permutations. Given a valid inversion sequence \(B' = (b'_1, b'_2, \dots, b'_n)\) (with \(0 \le b'_i \le n-i\)), one can reconstruct the unique permutation \(A\) by processing the inversion sequence from right to left. The algorithm is as follows:

[ \text{Let } F = [] \quad (\text{an initially empty list}) ]

[ \text{For } i \text{ from } n \text{ downto } 1:\quad \text{insert } i \text{ at index } b'_i \text{ in } F. ]

Using this algorithm, if there are multiple possible inversion sequences that extend the damaged \(B\), choosing \(0\) for every damaged position yields the lexicographically smallest permutation \(A\).

inputFormat

The first line contains a single integer \(n\) (the size of the permutation).
The second line contains \(n\) space-separated integers \(b_1, b_2, \dots, b_n\), where each \(b_i\) is either an integer in the range \([0, n-i]\) or \(-1\) indicating a damaged (unknown) position.

outputFormat

Output two lines:
The first line contains a single integer: the total number of valid permutations that agree with the given sequence \(B\).
The second line contains the lexicographically smallest permutation \(A\) (\(n\) space-separated integers).

sample

3
0 1 0

1
1 3 2