Let us define the derivatives of array in the following way:
You are given n numbers b0, ..., bn - 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 bk = 1 and strictly decreasing if bk = 0. Each element of array should be an integer from - 109 to 109, 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 b0, ..., bn - 1 (0 ≤ bi ≤ 1) separated by spaces. If bk = 1, k-th derivative of array should be strictly increasing, and if bk = 0 — strictly decreasing.
Output n integers a1, ..., an — the array which derivatives satisfy all the conditions specified by numbers b0, ..., bn - 1. The elements of the array should not exceed 109 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 109 by absolute value, output «IMPOSSIBLE».
3
1 1 1
1 2 5
3
0 0 1
-1 -2 -5
Name |
---|