Cho dãy số A gồm N số nguyên, các số được đánh số bắt đầu từ 1 đến N. Dãy này đối xứng nếu với mọi i thì ~A[i] = A[N-i+1]~. Ta có thể biến đổi dãy như sau: Lấy hai phần tử kề nhau và thay chúng bằng một phần tử có giá trị bằng tổng của hai phần tử đó.

Yêu cầu: Tính số lần thực hiện biến đổi ít nhất để biến dãy A thành dãy đối xứng.

Dữ liệu vào:

• Dòng 1: Chứa số nguyên N là số lượng phần tử của dãy ~(1 ≤ N ≤ 10^6)~.
• Dòng 2: Chứa N số nguyên dương thể hiện dãy A, các số không vượt quá ~10^9~.

Dữ liệu ra: Một số nguyên duy nhất là số lần biến đổi ít nhất có thể.

Ví dụ:

input 1

3
1 2 3

output 1

1

input 2

4
4 1 2 3

output 2

2

Ràng buộc:

• Có 30% số test ứng với 30% số điểm của bài có: ~1 ≤ N ≤ 10~
• Có 30% số test ứng với 30% số điểm của bài có: ~10 < N ≤ 1000~
• Có 40% số test còn lại không có ràng buộc gì thêm.