Problem: Farmer Drama

Want to try solving this problem? You can submit your code online if you log in or register.

Farmer Drama

Input File: farmin.txt
Output File: farmout.txt
Time Limit: 1 second
Memory Limit: 1 GB

Anna and Bob have purchased a farm in order to train for the Annual International Olympiad for Cows (AIOC). Anna's house is on the left side of the farm, and Bob's is on the right. The farm is currently divided into N plots of land of varying width by N-1 parallel fences.

However, Anna and Bob are displeased with this arrangement and each want their side of the farm to be identical to the other's to ensure fair training conditions. To resolve this situation, they agree to knock down some of the fences so that each plot is the same size as the corresponding plot on the opposite side; that is, the leftmost is the same size as the rightmost, the second leftmost the same size as the second rightmost, and so on. They begrudgingly agree that if this results in a plot in the exact middle of the farm, they will share it.

As knocking down fences is a time-consuming process, and Anna and Bob have difficulty getting along, you, an expert in the field, have been called in to determine the minimum number of fences that need to be knocked down in order to make Anna and Bob happy.

Input

The first line of input will contain a single integer N: the number of plots into which the farm is currently divided.

The second line will contain N space-separated integers, the ith integer w_i representing the initial width of the ith plot on the farm.

Output

Your program must output a single integer: the minimum number of fences you will need to knock down in order to satisfy Anna and Bob's demands. It is always possible to do so since a farm with all fences removed gives a single plot for Anna and Bob to share.

Sample Input

8
1 2 2 5 1 3 1 1

Sample Output

Explanation

You begin with the farm divided into plots as above. You knock down the fourth fence.

Then, you remove the second and fifth fences (of those that remain).

This results in a farm where Anna's side is identical to Bob's (with a middle section that they will have to share). In the process, you only knock down three fences, which is the smallest number possible.

Subtasks & Constraints

For all subtasks, 1 <= N <= 100,000, and 0 < w_i <= 10,000 for all i.

For Subtask 1 (10 marks), at most one fence will need to be knocked down to make both sides of the farm identical.
For Subtask 2 (20 marks), N <= 10.
For Subtask 3 (20 marks), all w_i will be either 1 or 2.
For Subtask 4 (20 marks), w_i <= 500.
For Subtask 5 (30 marks), no further constraints apply.