n weights are placed at equally spaced positions 1..n along a rigid beam (weight[i] at position i, 1-indexed; a weight may be negative, representing an upward lifting force). A position p (1 <= p <= n) is called a BALANCE POINT if the total torque of weights strictly to the left of p equals the total torque of weights strictly to the right of p, where the torque of a weight at position i relative to p is weight[i] * |i - p|. Formally, p is a balance point if:
sum over i < p of weight[i] * (p - i) == sum over i > p of weight[i] * (i - p)
(the weight at position p itself contributes to neither side; an empty side sums to 0). Find the SMALLEST position p that is a balance point. If no position balances, print -1.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, weight[1..n].
Output format
A single integer: the smallest balance point p, or -1 if none exists.
Constraints
- 1 <= n <= 100000
- -1000000 <= weight <= 1000000