A conveyor carries n parcels in a fixed order, each with an integer weight (a negative weight models a tare/credit adjustment). You must cut the belt at exactly one point so that every parcel before the cut goes to bin A and every parcel after the cut goes to bin B. Both bins must receive at least one parcel, so the cut is placed after position 1, 2, ..., or n-1. Report the minimum possible absolute difference between the total weight in bin A and the total weight in bin B.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the parcel weights in belt order.
Output format
A single integer: the minimum absolute difference between the two bins' total weights.
Constraints
- 2 <= n <= 100000
- -1000000 <= each weight <= 1000000