Prefix Permutation - Repovive Starter Round 9 | Repovive

25D. Prefix Permutation

2000 pts2s256 MB

You are given an array $b$ of $n$ nonnegative integers.

Construct an integer array $a$ of length $n$ such that:

$-1 \le a_i \le b_i$ for every $i$ .
The prefix sums $a_1, a_1+a_2, \ldots, a_1+a_2+\cdots+a_n$ contain each integer from $1$ to $n$ exactly once.

If no such array exists, output $-1$ . Otherwise, output any valid array.

Constraints

$1 \le n \le 2 \times 10^5$
$0 \le b_i \le n$
All input values are integers.

Input

\begin{array}{l} n \\ b_1 \quad b_2 \quad \cdots \quad b_n \end{array}

Output

a_1 \quad a_2 \quad \cdots \quad a_n

If no valid array exists:

-1

Samples

Input

6
2 0 4 0 0 3

Explanation

The prefix sums are $2,1,5,4,3,6$ , so each integer from $1$ to $6$ appears exactly once. Every element of the output also satisfies its corresponding bound.

Output

2 -1 4 -1 -1 3

Input

4
2 0 2 0

Explanation

The first prefix sum must be $1$ or $2$ . If it is $1$ , no allowed value of $a_2$ gives a new positive prefix sum. If it is $2$ , then $a_2=-1$ is forced. The third prefix sum is then at most $3$ , so it must be $3$ . Since $a_4\le 0$ , the fourth prefix sum cannot be the remaining value $4$ . Thus no valid array exists.

Output

-1

Input

1
1

Explanation

The only prefix sum is $1$ , and $-1\le a_1\le b_1$ holds.

Output

You are given an array $b$ of $n$ nonnegative integers.

Construct an integer array $a$ of length $n$ such that:

$-1 \le a_i \le b_i$ for every $i$ .
The prefix sums $a_1, a_1+a_2, \ldots, a_1+a_2+\cdots+a_n$ contain each integer from $1$ to $n$ exactly once.

If no such array exists, output $-1$ . Otherwise, output any valid array.

$1 \le n \le 2 \times 10^5$
$0 \le b_i \le n$
All input values are integers.

\begin{array}{l} n \\ b_1 \quad b_2 \quad \cdots \quad b_n \end{array}

a_1 \quad a_2 \quad \cdots \quad a_n

If no valid array exists:

-1

The prefix sums are $2,1,5,4,3,6$ , so each integer from $1$ to $6$ appears exactly once. Every element of the output also satisfies its corresponding bound.

The only prefix sum is $1$ , and $-1\le a_1\le b_1$ holds.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

25D. Prefix Permutation

Constraints

Input

Output

Samples

25D. Prefix Permutation

Constraints

Input

Output

Samples