Mislav rất yêu thích dãy đối xứng. Hãy giúp cậu bé giải quyết bài tập sau!

Cho dãy ~A~ gồm ~N~ số nguyên. Chúng ta gọi A là dãy đối xứng nếu ~A[i] = A[N-i+1]~ với mọi ~i~ ~(1 \le i \le N)~, trong đó ~A[i]~ là phần tử thứ ~i~ của dãy ~A~ và chỉ số của phần tử đầu tiên trong dãy là ~1~.

Mislav có thể biến đổi dãy theo cách sau: trong một bước, cậu bé chọn hai phần tử liền kề của dãy đó và thay thế ~2~ 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 ~1~ sau mỗi bước biến đổi.

Mislav muốn biết số bước biến đổi tối thiểu mà cậu phải thực hiện để dãy ban đầu trở thành dãy đối xứng.

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \le N \le 10^6)~ cho biết số phần tử trong dãy.

• Dòng tiếp theo chứa ~N~ số nguyên dương được ngăn cách bởi dấu cách, cho biết các phần tử trong dãy của Mislav. Các số này có giá trị không vượt quá ~10^9~.

Output

In ra một số nguyên duy nhất là số bước biến đổi tối thiểu để biến dãy ban đầu thành một dãy đối xứng, dựa trên các quy tắc đã cho.

Sample 1

Input

3
1 2 3

Output

1

Giải thích:

1 2 3 ~\rightarrow~ 3 3

Sample 2

Input

5
1 2 4 6 1

Output

1

Giải thích:

1 2 4 6 1 ~\rightarrow~ 1 6 6 1

Sample 3

Input

4
1 4 3 2

Output

2

Giải thích:

1 4 3 2 ~\rightarrow~ 5 3 2 ~\rightarrow~ 5 5

Scoring

• ~9~ test đầu có ~N \le 10~.
• ~9~ test tiếp theo có ~N \le 1000~.
• ~12~ test còn lại không có ràng buộc gì thêm.