Problem
Gần đây, Risotto Nero đã tìm hiểu về tháp Hà Nội và anh ấy rất thích câu đố này. Tuy nhiên, chơi trên giấy đã chán nên anh quyết định tái hiện chúng ngoài đời thực.
Tuy nhiên, Risotto Nero chỉ có những chiếc nhẫn có cùng bán kính nên anh ấy đã nghĩ ra một câu đố khác.
Có n que tính. Ban đầu, mỗi người trong số họ có chính xác một chiếc nhẫn hoặc không có chiếc nhẫn nào. Đồng thời, trên bất kỳ que nào cũng có ít nhất một chiếc nhẫn.
Chỉ với một thao tác, bạn có thể chuyển chiếc nhẫn sang một cây đũa liền kề.
Cần số lượng hành động tối thiểu để đạt được tình huống sao cho một số nguyên k > 1 sao cho số vòng trên mỗi que chia hết cho k, hay nói rằng điều này là không thể.
Risotto Nero đã giải quyết vấn đề này và đang chờ bạn kiểm tra câu trả lời của mình.
Đầu vào:
Dòng đầu tiên chứa một số nguyên n (1 ≤ n ≤ 10
5) — số que tính.
Dòng thứ hai chứa n số nguyên a
1,a
2,…,a
n (0 ≤ a_i ≤ 1) — số vòng ban đầu trên mỗi que.
Đầu ra:
Nếu giải pháp cần thiết không tồn tại, hãy in −1.
Nếu không thì in x — số lượng hành động tối thiểu để đưa câu đố về trạng thái mong muốn.
Ví dụ:
| Đầu vào |
Đầu ra |
3
1 0 1
| 2 |
1
1 |
-1 |
Giải thích:
Trong ví dụ đầu tiên, trước tiên bạn có thể di chuyển chiếc nhẫn từ thanh thứ ba sang thanh thứ hai, sau đó từ thanh thứ hai sang thanh thứ nhất. Sau đó, số vòng trên mỗi que sẽ được chia cho 2.