Gửi kẹo cho Alice

Có $n$ chiếc hộp xếp thành một hàng, đánh số từ $1$ đến $n$. Ban đầu hộp thứ $i$ chứa $a_i$ viên kẹo. Đảm bảo có ít nhất một hộp chứa số kẹo dương.

Trong một giây, ta có thể lấy một viên kẹo từ hộp $i$ và chuyển sang hộp $i-1$ hoặc hộp $i+1$ (nếu hộp đó tồn tại).

Ta muốn tồn tại một số nguyên $k>1$ sao cho số kẹo trong mỗi hộp đều chia hết cho $k$ (một hộp rỗng, tức chứa $0$ viên, luôn được coi là chia hết cho $k$).

Hãy tính số giây ít nhất cần thực hiện để đạt được mục tiêu trên. Nếu không có cách nào, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là số hộp kẹo.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ là số kẹo trong mỗi hộp.

Dữ liệu ra

• In ra một số nguyên là số giây ít nhất cần thiết, hoặc $-1$ nếu không thể.

Ràng buộc

• $1\le n\le {10}^6$
• $0\le a_i\le {10}^6$
• Có ít nhất một $a_i$ dương.

Ví dụ