SnarkNews Summer Series - 2008
Round 2
Задачи [A] [B] [C] [D] [E] [F]

Склад

Time limit = 2s, Input File: input.txt, Output File: output.txt

В связи с быстрым ростом объёмов продаж техники компания "HangUp Computers" приняла решение о строительстве нового склада USB-дисков "Алеф-0".

Новый склад компании представляет собой бесконечную последовательность ячеек, занумерованных целыми числами. Для удобства персонала товар сгруппирован так, что на данный момент номер каждой ячейки, занятой товаром, по модулю не превосходит 1000. Общее количество USB-дисков на складе "Алеф-0" равно N<10000. При этом оказалось, что в некоторых ячейках находится более одного USB-диска (для не знакомых с техникой — количество USB-дисков в ячейке — целое неотрицательное число). Не вполне удовлетворённое эффективностью использования склада руководство компании издало приказ об инвентаризации на складе, которая должна выполняться следующим образом (далее следует приложение к приказу):

"Инвентаризация проходит в несколько одинаковых этапов.

Этап инвентаризации начинается с ячейки с наименьшим номером из тех, которые заняты на момент начала этапа, и состоит в следующем:

Для каждой ячейки, следуя по возрастанию, последовательно выполняются следующие действия:

До тех пор, пока в текущей ячейке больше 1 дисков, проводятся операции разноса: один диск из ячейки переносится в ячейку со следующим номером, а другой — в ячейку с номером, на 2 меньшим, чем текущий номер ячейки. Одна такая двойная перестановка считается одной операцией разноса.

Этап инвентаризации заканчивается, если все ячейки с номерами, большими текущей, пусты, а в текущей ячейке находится ровно один диск.

Инвентаризация заканчивается, если в каждой занятой ячейке находится не более одного диска."

Вам необходимо выяснить, закончится ли инвентаризация, и если она закончится — то вывести число операций, необходимых для её завершения.

Вход 0 < N < 10000 — общее количество USB-дисков на складе "Алеф-0", далее с новой строки N целых чисел в интервале от -1000 до 1000, обозначающих номер ячейки, в которой расположен данный диск. Остальные ячейки склада являются пустыми. В одной ячейке может находиться не более 10002 дисков.

Выход Если инвентаризация не закончится, вывести -1. Иначе вывести число операций разноса, применённых в процессе инвентаризации.

Вход#1
4
-100 -100 -100 -100
Выход#1
5