coci 2012/2013 contest1 2_F7- F7(챔피언) > 문제은행 : 정보올림피아드&알고리즘




4349 : F7(챔피언)

제한시간
1000 ms   
메모리제한
16 MB   
해결횟수
4 회   
시도횟수
20 회   

문제

가상의 자동차 레이스인 포뮬러 세븐(Formula 7)의 

챔피언은 여러 대회를 치른 결과로 결정한다. 

레이서들은 각 대회에서 얻은 점수들의 총 합을 가지고 

최고점을 얻은 레이서가 챔피언이 된다. 

포뮬러 지로는 현재 마지막 대회를 앞두고 있다. 

이 시점에서 레이서들 중에서 챔피언이 될 수 있는 

가능성이 남아있는 레이서들의 총 수를 알고자 한다.

 

포뮬러 지로에는 N명의 레이서들이 참가하고 있다. 

그들은 각 대회에서 점수들을 얻는다. 

한 대회의 우승자는 N점을 획득하고, 2등은 N-1점, 3등은 N-2점, ..., 

꼴등은 1점을 얻는다.

어떠한 두 레이서도 종착지점에 같은 시각에 들어오지 않는다고 가정한다. 

다시 말해서, 동일 등수의 레이서들은 존재하지 않는다. 

문제는 마지막 대회 직전에 각 레이서가 얻은 점수들의 합이 주어질 때, 

마지막 대회의 결과에 따라서 여전히 챔피언이 될 수 있는, 

다시 말해서, 가장 큰 총점을 얻을 수 있는 가능성이 있는 레이서들의 수를 출력하는 것이다. 

둘 이상의 레이서들이 같은 최대 총점을 얻은 경우에는 모두가 챔피언이 된다. ​

 


입력형식

입력의 첫째 줄에는 포뮬러 지로에 참가한 레이서들의 수를 나타내는 정수

N(3≤ N ≤ 300,000)이 주어진다. 

다음 이어지는 N개의 줄에서 i번째 줄은 하나의 정수 

Ti (3 ≤ Ti ≤ 2,000,000)를 포함한다.

Ti는 i번째 레이서가 마지막 대회 전에 얻은 점수들의 합을 나타낸다.​ 


출력형식

출력은 정확히 한 줄로 주어진다. 

여기에는 여전히 챔피언이 될 가능성이 남아 있는

레이서들의 수를 나타내는 정수가 주어진다. ​ 


입력 예

3
8
10
9

출력 예

3

입력 예

5
15
14
15
12
14

출력 예

4


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP