Cho dãy gồm số nguyên gồm ~n~ phần tử ~A = \{a_1 , a_2, \ldots, a_n \}~. Dãy được gọi là Palindrome nếu ta in ra theo thứ tự từ trái sang phải cũng giống như từ phải sang trái. Nói cách khác có thể cụ thể hóa thành công thức a[i] = a[n - i + 1], ~\forall i \in [1..n]~.

Cho trước một dãy số ~A~ có thể là chưa phải là Palindrome, ta biến đổi dãy theo cách sau: trong một bước, chọn hai phần tử liền kề của dãy đó và thay thế số này bằng tổng của chúng. Lưu ý rằng số phần tử trong dãy sẽ giảm đi sau mỗi bước biến đổi.

Hỏi số bước biến đổi tối thiểu mà ta phải thực hiện để dãy ban đầu trở thành dãy Palindrome là bao nhiêu?

Input

Dòng đầu tiên chứa số nguyên dương ~n~ thỏa ~1 \le n \le 10^6~.

Dòng tiếp theo chứa ~n~ số nguyên ~a_i~ thỏa ~1 \le a_i \le 10^9~.

Output

In kết quả cần tìm.

Samples

Sample Input 1

3
1 2 3

Sample Output 1

1

Sample Input 2

4
1 4 3 2

Sample Output 2

2