Рабочее место участника

Том разрабатывает игру-платформер про Марсио, первого исследователя Марса. После разработки уровней Том подсчитал их сложность - сумму минимального необходимого количества прыжков и выстрелов для прохождения уровня. Некоторые начальные уровни игры оказались слишком сложными по этой оценке, и Том решил убрать некоторые препятствия и врагов с начальных уровней, чтобы сложность уровней шла в строго возрастающем порядке.

Так как добавление новых препятствий на уровень является более сложной задачей, то Том хочет минимизировать суммарное количество добавлений новых препятствий и врагов. С другой стороны Том хочет максимально сохранить уже имеющиеся препятствия и нужно минимизировать суммарное количество удаляемых препятствий. Также сложность самого первого уровня игры не должна быть меньше 1.

Первая строка ввода содержит одно целое число `N` (`1 <= N <= 100000`) - количество уровней в игре. Далее следует `N` строк, содержащих по одному целому числу от 1 до `10^6` - начальная сложность уровней до изменений.

Вывести `N` строк по одному числу строке - минимальные изменения, которые нужно сделать на этом уровне. Отрицательное число означает, что сложность уровня нужно уменьшить на соответствующую величину, положительное число - что сложность нужно увеличить на эту величину, 0 - что сложность уровня можно оставить без изменений. Если существует несколько вариантов, то вывести вариант, в котором суммарное количество добавлений на всех уровнях минимально. Если существует несколько таких вариантов с минимальных количеством добавлений, то вывести тот вариант из них, в котором суммарное количество удаляемых препятствий минимально.

3
5
5
5

-2
-1
0

4
5
1
7
5

-4
1
-3
0