동물 괴롭힘

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

요약

서로 다른 힘을 가진 n마리 동물이 각자 최선으로 행동할 때, 공격과 방어가 끝난 뒤 살아남는 동물 수를 구합니다.

난이도: 보통10점 중 7점
유형: 정렬, 게임 이론, 그리디
정답자: 아직 제출이 없습니다

문제

힘의 세기가 서로 다른 동물들이 물웅덩이에서 물을 마신다. 물웅덩이에 동물이 많을수록 각 동물이 받는 물의 양은 줄어든다. 그래서 일부 동물은 다른 동물들을 강제로 떠나게 하려고 한다.

주기적으로 가장 약한 동물이 더 강한 동물들의 공격을 받을 수 있다. 다른 동물들은 가장 약한 동물을 도우러 올 수 있다. 공격자들의 힘의 합이 방어자들의 힘의 합보다 엄격히 크면 가장 약한 동물은 떠난다. 나머지 방어자들은 남는다. 이 과정은 몇 번이고 반복될 수 있다.

신진 동물학자인 당신은 동물들이 논리적으로 생각하는지 알고 싶다. 각 동물은 자신은 제거되지 않으면서 다른 동물을 최대한 많이 제거하려고 한다. 각 동물이 항상 자신의 이익에 가장 맞는 결정을 내린다고 가정할 때, 모든 공격이 끝난 뒤 확실히 남아 있는 동물의 수를 구하라.

입력

첫째 줄에 동물의 수 $n$ ( $1 \le n \le 5 \times 10^5$ )이 주어진다.

다음 $n$ 개 줄에는 각각 동물의 힘의 세기 $s$ ( $1 \le s \le 10^9$ )가 한 줄에 하나씩 주어진다. 힘의 세기는 모두 서로 다르다.

출력

확실히 남아 있는 동물의 수를 한 줄에 출력한다.

예제2

예제 1
입력
```
4
3
4
8
9
```
예상 출력
```
3
```
예제 2
입력
```
8
20
1
2
13
9
5
8
61
```
예상 출력
```
1
```