Lazy to Win

Alexey is probably the smartest and at the same time the laziest person in the world. Today he is participating in the Olympiad.

At the Olympiad, participants are given $n$ problems. A participant receives $a_i$ points for a correct solution of the $i$-th problem. No points are given for an incorrect solution. Participants who receive at least half of the total points are awarded a winner's diploma. For example, if there are three problems worth $1$, $3$, and $4$ points, a participant needs four points to earn the diploma.

Alexey came to the Olympiad to get a winner's diploma. He can correctly solve any problem. He is also very lazy and wants to solve as few problems as possible.

Alexey chooses his problems lazily too. He picks a problem number $k$, then solves problems $k, k+1, k+2, \ldots$ until he has enough points for a diploma. He allows himself to skip at most one problem, if skipping it lets him solve fewer problems in the end.

Determine the minimum number of problems Alexey needs to solve with this strategy to get the winner's diploma.

On the first line there is one integer $n$, the number of problems ($1 \le n \le 10^5$).

On the second line there are $n$ integers $a_1, a_2, \ldots, a_n$, the cost of each problem in points ($1 \le a_i \le 10^9$).

On the first line, output a single integer: the minimum number of problems Alexey needs to solve with his strategy to get the winner's diploma.

In the first example, participants need at least four points to get the winner's diploma. Alexey can start solving the third problem, then skip the fourth problem and get four points by solving two tasks.

In the second example, it is enough to solve only the second problem to receive three points.