I. Производная массива
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Определим производные массива следующим образом:

  • Нулевой производной массива a1, ..., an называется сам этот массив a1, ..., an.
  • Первой производной массива a1, ..., an, где n > 1, называется массив a'1, ..., a'n - 1, такой, что для всех i = 1,  ...,  n - 1 выполняется равенство a'i = ai + 1 - ai.
  • k-ой производной массива a1, ..., an, где 1 < k < n, называется (k - 1)-ая производная массива a'1, ..., a'n - 1.

Даны n чисел b0, ..., bn - 1, каждое из которых равно либо нулю, либо единице. Постройте массив длины n такой, что его k-я производная строго возрастает, если bk = 1, и строго убывает, если bk = 0. Каждый элемент массива должен быть целым числом от  - 109 до 109. Если это невозможно, выведите «IMPOSSIBLE».

Входные данные

В первой строке записано единственное целое число n (1 ≤ n ≤ 2000) — длина массива, который надо построить.

Во второй строке через пробел записаны n целых чисел b0, ..., bn - 1 (0 ≤ bi ≤ 1). Если bk = 1, то k-я производная массива должна строго возрастать, а если bk = 0 — строго убывать.

Выходные данные

Выведите n целых чисел a1, ..., an — массив, производные которого удовлетворяют всем ограничениям, заданными числами b0, ..., bn - 1. Элементы массива не должны превышать по модулю 109.

Если существует несколько таких массивов, выведите любой.

Если же такого массива не существует, или его элементы превышают по модулю 109, выведите «IMPOSSIBLE».

Примеры
Входные данные
3
1 1 1
Выходные данные
1 2 5
Входные данные
3
0 0 1
Выходные данные
-1 -2 -5