게으르게 이기기

알렉세이는 세상에서 아마 가장 똑똑하면서 동시에 가장 게으른 사람이다. 오늘 그는 올림피아드에 참가한다.

올림피아드에서는 참가자에게 $n$개의 문제가 주어진다. 참가자가 $i$번째 문제를 맞히면 $a_i$점을 받는다. 틀린 풀이에는 점수가 없다. 전체 점수의 절반 이상을 받은 참가자는 입상 증서를 받는다. 예를 들어 문제가 1점, 3점, 4점짜리 세 개라면 입상 증서를 받으려면 4점이 필요하다.

알렉세이는 입상 증서를 받기 위해 올림피아드에 왔다. 그는 어떤 문제든 정확히 풀 수 있다. 하지만 매우 게을러서 가능한 한 적은 문제만 풀고 싶어 한다.

그는 풀 문제도 게으르게 고른다. 문제 번호 $k$를 하나 고른 뒤, 입상 증서를 받는 데 충분한 점수가 모일 때까지 $k, k+1, k+2, \ldots$ 번 문제를 차례로 푼다. 그는 문제를 한 개까지 건너뛸 수 있다. 건너뛰면 결국 푸는 문제 수가 줄어드는 경우에 한해서다.

이 전략으로 입상 증서를 받기 위해 알렉세이가 풀어야 하는 문제 수의 최솟값을 구하라.

첫 번째 줄에 문제의 개수 $n$이 주어진다 ($1 \le n \le 10^5$).

두 번째 줄에는 각 문제의 점수 $a_1, a_2, \ldots, a_n$이 $n$개의 정수로 주어진다 ($1 \le a_i \le 10^9$).

첫 번째 줄에 알렉세이가 이 전략으로 입상 증서를 받기 위해 풀어야 하는 문제 수의 최솟값을 정수 하나로 출력한다.

첫 번째 예제에서 참가자는 입상 증서를 받으려면 최소 4점이 필요하다. 알렉세이는 세 번째 문제부터 풀기 시작해 네 번째 문제를 건너뛰고, 두 문제를 풀어 4점을 얻을 수 있다.

두 번째 예제에서는 두 번째 문제만 풀어 3점을 얻으면 충분하다.