Lazy to Win

면접 대비

시간 제한1초메모리 제한1024 MB

요약

Alexey는 어떤 k부터 연속으로 문제를 풀되 한 문제는 건너뛸 수 있으며, 총점의 절반 이상을 얻기 위해 풀어야 하는 최소 문제 수를 구한다. It should be correct: the Korean sentence is fine:

난이도: 보통10점 중 5점
유형: 배열, 누적 합, 이분 탐색, 그리디
정답자: 아직 제출이 없습니다

문제

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. The participant will receive $a\_i$ points for the correct solution of the $i$ -th problem. No points are given for an incorrect solution. The winner's diplomas will be awarded to those participants who receive at least half of the total number of points. For example, if there are given three problems at the Olympiad, the cost of which in points are $1$ , $3$ and $4$ , it is enough to receive four points to be awarded the winner's diploma.

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

Alexey is so lazy that he even lazily chooses tasks that he will solve. He wants to choose some problem with the number $k$ , and then solve problems with the numbers $k, k+1, k+2 \ldots$ until he has enough points to get a winner's diploma. The maximum that Alexey is ready for is to skip one problem and not solve it, in order to solve even fewer problems in the end.

Determine the minimum number of problems that Alexey needs to solve using his strategy to get the winner's diploma.

입력

On the first line there is one integer $n$ --- the number of problems that were given at the Olympiad ( $1 \le n \le 10^5$ ).

On the second line there are $n$ integers $a\_1, a\_2, \dots a\_n$ --- the cost of each problem in points ( $1 \le a\_i \le 10^9$ ).

출력

On the first line output single integer --- the minimum number of problems that Alexey needs to solve using his strategy to get the winner's diploma.

힌트

In the first example, participants need receive 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 and receive three points.

예제2

예제 1
입력
```
5
1 1 2 1 2
```
예상 출력
```
2
```
예제 2
입력
```
3
2 3 1
```
예상 출력
```
1
```