시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 516 168 122 34.463%

문제

권위를 자랑하는 레이싱 대회 F7이 열릴 예정이다. F7은 드라이버의 순위가 자주 바뀌기 때문에 사람들에게 인기가 아주 많다. 상근이는 F7 레이싱의 엄청난 팬이지만, 마지막 레이싱과 중간고사가 겹쳐서 갈 수 없게 되었다.

지금은 마지막 레이싱을 제외한 나머지 레이싱이 모두 종료된 상황이다. 상근이는 우승을 할 수 있는 사람의 수를 알아보려고 한다. F7의 우승자는 각 레이싱을 통해서 얻은 점수의 합이며, 점수가 가장 높은 사람이 우승을 하게 된다.

레이싱에서 1등을 한 사람은 N점을 얻게 되고, 2등은 N-1점, ..., 꼴등은 1점을 얻게 된다. 각 레이싱에서 두 드라이버의 등수가 같은 경우는 없다.

마지막 레이싱을 하기 바로 전에 각 드라이버의 점수가 주어졌을 때, 우승을 할 가능성이 있는 사람의 수를 구하는 프로그램을 작성하시오. 만약 점수의 합이 가장 큰 사람이 여러 명이라면, 두 사람 다 우승자이다.

입력

첫째 줄에 F7에 참가하는 드라이버의 수 N (3 ≤ N ≤ 300,000)이 주어진다.

다음 N개 줄에는 각 드라이버가 마지막 레이싱을 하기 전까지 얻은 점수 Bi가 주어진다. (0 ≤ Bi ≤ 2,000,000, i = 1, ..., N)

출력

첫째 줄에 F7을 우승할 가능성이 있는 사람의 수를 출력한다.

예제 입력

3
8
10
9

예제 출력

3

힌트