Недавно Ризотто Нэро узнал про ханойские башни, и эта головоломка очень ему понравилась. Однако играть на бумаге ему надоело, поэтому он решил воспроизвести их в реальной жизни.
Однако у Ризотто Нэро были кольца только одинакового радиуса, поэтому он придумал другую головоломку.
Есть n палочек. Изначально на каждую из них либо надето ровно одно кольцо, либо ни одного. При этом как минимум одно кольцо присутствует на какой-либо из палочек.
За одно действие можно перенести кольцо на соседнюю палочку.
Необходимо за минимальное количество действий добиться такой ситуации, чтобы нашлось какое-то целое число k > 1, такое, что количество колец на каждой из палочек делилось бы на k, или сказать, что это невозможно.
Ризотто Нэро уже решил эту задачу и ждет вас, чтобы сверить ответы.
Входные данные:
Первая строка содержит одно целое число n (1 ≤ n ≤ 10
5) — количество палочек.
Вторая строка содержит n целых чисел a
1,a
2,…,a
n (0 ≤ a_i ≤ 1) — изначальное количество колец на каждой из палочек.
Выходные данные:
Если необходимого решения не существует выведите −1.
Иначе выведите x — минимальное количество действий, чтобы привести головоломку в необходимое состояние.
Примеры:
| Входные данные |
Выходные данные |
3
1 0 1 |
2 |
1
1 |
-1 |
Пояснение:
В первом примере можно сперва переместить кольцо с третей палочки на вторую, потом со второй на первую. После этого количество колец на каждой из палочек будет делиться на 2.