Module: 그리디 알고리즘

Problem

최근에 Risotto Nero는 하노이의 탑에 대해 알게 되었고 그는 이 퍼즐을 정말 좋아했습니다. 그러나 그는 종이 위에서 노는 것이 지겨워 실생활에서 재현하기로 결정했습니다.
그러나 Risotto Nero는 반지름이 같은 반지밖에 없었기 때문에 다른 퍼즐을 생각해 냈습니다.
n개의 막대기가 있습니다. 처음에는 각각 정확히 하나의 링이 있거나 전혀 없습니다. 동시에 스틱에 적어도 하나의 링이 있습니다.
한 번의 작업으로 반지를 인접한 지팡이로 옮길 수 있습니다. 
어떤 정수 k > 각 막대기에 있는 고리의 수가 k로 나누어질 수 있도록 1이거나 이것이 불가능하다고 말합니다.
Risotto Nero는 이미 이 문제를 해결했으며 귀하의 답을 확인하기를 기다리고 있습니다.

입력:
첫 번째 줄에는 단일 정수 n(1 ≤ n ≤ 10⁵)이 포함됩니다. 스틱의 수.
두 번째 줄에는 n개의 정수 a₁,a₂,…,a_n(0 ≤ a_i ≤ 1) — 각 스틱의 초기 링 수입니다.

출력:
필요한 솔루션이 없으면 -1을 인쇄합니다.
그렇지 않으면 x — 퍼즐을 원하는 상태로 만들기 위한 최소 작업 수입니다.

예:
  <몸>
설명:
첫 번째 예에서는 먼저 링을 세 번째 스틱에서 두 번째 스틱으로 이동한 다음 두 번째 스틱에서 첫 번째 스틱으로 이동할 수 있습니다. 그런 다음 각 스틱의 링 수를 2로 나눕니다.

입력	출력
3 1 0 1	2
1 1	-1