400469: GYM100187 I Derivative of Array

Let us define the derivatives of array in the following way:

• Zeroth derivative of array a₁, ..., a_n is defined as this array a₁, ..., a_n itself.
• First derivative of array a₁, ..., a_n, where n > 1, is defined as such an array a'₁, ..., a'_n - 1, that for all i = 1,  ...,  n - 1 the equality a'_i = a_i + 1 - a_i is satisfied.
• k-th derivative of array a₁, ..., a_n, where 1 < k < n, is defined as (k - 1)-th derivative of array a'₁, ..., a'_n - 1.

You are given n numbers b₀, ..., b_n - 1, each equals either to zero or to one. You are to build an array of length n so that its k-th derivative is strictly increasing if b_k = 1 and strictly decreasing if b_k = 0. Each element of array should be an integer from  - 10⁹ to 10⁹, inclusively. If it is impossible, output «IMPOSSIBLE».

The first line contains the only integer n (1 ≤ n ≤ 2000) — the length of the array you are to build.

The second line contains n integers b₀, ..., b_n - 1 (0 ≤ b_i ≤ 1) separated by spaces. If b_k = 1, k-th derivative of array should be strictly increasing, and if b_k = 0 — strictly decreasing.

Output n integers a₁, ..., a_n — the array which derivatives satisfy all the conditions specified by numbers b₀, ..., b_n - 1. The elements of the array should not exceed 10⁹ by absolute value.

If there are several such arrays, you can output any of them.

If there is no such array or some of its elements are greater than 10⁹ by absolute value, output «IMPOSSIBLE».

3
1 1 1

1 2 5

3
0 0 1

-1 -2 -5