Recover the Missing Array Elements

Dream had an array of n positive integers \(a_1, a_2, \dots, a_n\) where \(1 \le a_i \le 1000\) and \(1 \le n \le 10^5\). He computed the prefix sums \(p_i = a_1+a_2+\dots+a_i\). In the original array, the prefix sums were strictly increasing, i.e. for any \(1 \le i < n\), \(p_i < p_{i+1}\).

However, Tommy stole this array and replaced several elements of the prefix sum array with \(-1\). You are given the modified prefix sum array \(p_1, p_2, \dots, p_n\) (where a value \(-1\) denotes a missing element). Your task is to recover any valid array \(a_1, a_2, \dots, a_n\) that would yield a strictly increasing prefix sum sequence and respects \(1 \le a_i \le 1000\) as well as the given known prefix sums.

It is guaranteed that there exists at least one solution.

inputFormat

The first line contains an integer \(n\) (the length of the array). The second line contains \(n\) integers \(p_1, p_2, \dots, p_n\) separated by spaces, where each \(p_i\) is either a positive integer representing the prefix sum up to \(i\) or \(-1\) if the original value is missing.

Note: When \(p_i \neq -1\), it represents the true prefix sum \(a_1+a_2+\dots+a_i\) as computed originally.

outputFormat

Output a single line containing \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) which form a valid array satisfying the constraints \(1 \le a_i \le 1000\) and the given (non-missing) prefix sum conditions.

sample

3
-1 5 -1

4 1 1