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.
The second line will contain N space-separated integers, the ith integer wi representing the initial width of the ith plot on the farm.
8 1 2 2 5 1 3 1 1
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.
For all subtasks, 1 <= N <= 100,000, and 0 < wi <= 10,000 for all i.