시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1051 309 242 31.510%

문제

권위를 자랑하는 레이싱 대회 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을 우승할 가능성이 있는 사람의 수를 출력한다.

예제 입력 1

3
8
10
9

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjI3OTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJGNyIsImRlc2NyaXB0aW9uIjoiPHA+XHVhZDhjXHVjNzA0XHViOTdjIFx1Yzc5MFx1Yjc5MVx1ZDU1OFx1YjI5NCBcdWI4MDhcdWM3NzRcdWMyZjEgXHViMzAwXHVkNjhjIEY3XHVjNzc0IFx1YzVmNFx1YjliNCBcdWM2MDhcdWM4MTVcdWM3NzRcdWIyZTQuIEY3XHVjNzQwIFx1YjRkY1x1Yjc3Y1x1Yzc3NFx1YmM4NFx1Yzc1OCBcdWMyMWNcdWM3MDRcdWFjMDAgXHVjNzkwXHVjOGZjIFx1YmMxNFx1YjAwY1x1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjMGFjXHViNzhjXHViNGU0XHVjNWQwXHVhYzhjIFx1Yzc3OFx1YWUzMFx1YWMwMCBcdWM1NDRcdWM4ZmMgXHViOWNlXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgRjcgXHViODA4XHVjNzc0XHVjMmYxXHVjNzU4IFx1YzVjNFx1Y2NhZFx1YjA5YyBcdWQzMmNcdWM3NzRcdWM5YzBcdWI5Y2MsIFx1YjljOFx1YzljMFx1YjljOSBcdWI4MDhcdWM3NzRcdWMyZjFcdWFjZmMgXHVjOTExXHVhYzA0XHVhY2UwXHVjMGFjXHVhYzAwIFx1YWNiOVx1Y2NkMFx1YzExYyBcdWFjMDggXHVjMjE4IFx1YzVjNlx1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzljMFx1YWUwOFx1Yzc0MCBcdWI5YzhcdWM5YzBcdWI5YzkgXHViODA4XHVjNzc0XHVjMmYxXHVjNzQ0IFx1YzgxY1x1YzY3OFx1ZDU1YyBcdWIwOThcdWJhMzhcdWM5YzAgXHViODA4XHVjNzc0XHVjMmYxXHVjNzc0IFx1YmFhOFx1YjQ1MCBcdWM4ODVcdWI4Y2NcdWI0MWMgXHVjMGMxXHVkNjY5XHVjNzc0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNmIwXHVjMmI5XHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVjNTRjXHVjNTQ0XHViY2Y0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gRjdcdWM3NTggXHVjNmIwXHVjMmI5XHVjNzkwXHViMjk0IFx1YWMwMSBcdWI4MDhcdWM3NzRcdWMyZjFcdWM3NDQgXHVkMWI1XHVkNTc0XHVjMTFjIFx1YzViYlx1Yzc0MCBcdWM4MTBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzc0XHViYTcwLCBcdWM4MTBcdWMyMThcdWFjMDAgXHVhYzAwXHVjN2E1IFx1YjE5Mlx1Yzc0MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjNmIwXHVjMmI5XHVjNzQ0IFx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1YzljMFx1YjljOSBcdWI4MDhcdWM3NzRcdWMyZjFcdWM1ZDBcdWMxMWMgMVx1YjRmMVx1Yzc0NCBcdWQ1NWMgXHVjMGFjXHViNzhjXHVjNzQwIE5cdWM4MTBcdWM3NDQgXHVjNWJiXHVhYzhjIFx1YjQxOFx1YWNlMCwgMlx1YjRmMVx1Yzc0MCBOLTFcdWM4MTAsIC4uLiwgXHVhZjM0XHViNGYxXHVjNzQwIDFcdWM4MTBcdWM3NDQgXHVjNWJiXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVhYzAxIFx1YjgwOFx1Yzc3NFx1YzJmMVx1YzVkMFx1YzExYyBcdWI0NTAgXHViNGRjXHViNzdjXHVjNzc0XHViYzg0XHVjNzU4IFx1YjRmMVx1YzIxOFx1YWMwMCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjOWMwXHViOWM5IFx1YjgwOFx1Yzc3NFx1YzJmMVx1Yzc0NCBcdWQ1NThcdWFlMzAgXHViYzE0XHViODVjIFx1YzgwNFx1YzVkMCBcdWFjMDEgXHViNGRjXHViNzdjXHVjNzc0XHViYzg0XHVjNzU4IFx1YzgxMFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM2YjBcdWMyYjlcdWM3NDQgXHVkNTYwIFx1YWMwMFx1YjJhNVx1YzEzMVx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHViOWNjXHVjNTdkIFx1YzgxMFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3NzQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjNWVjXHViN2VjIFx1YmE4NVx1Yzc3NFx1Yjc3Y1x1YmE3NCwgXHVjNWVjXHViN2VjXHViYTg1IFx1YjJlNCBcdWM2YjBcdWMyYjlcdWM3OTBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIEY3XHVjNWQwIFx1Y2MzOFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWI0ZGNcdWI3N2NcdWM3NzRcdWJjODRcdWM3NTggXHVjMjE4IE4gKDMgJmxlOyBOICZsZTsgMzAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YjRkY1x1Yjc3Y1x1Yzc3NFx1YmM4NFx1YWMwMCBcdWI5YzhcdWM5YzBcdWI5YzkgXHViODA4XHVjNzc0XHVjMmYxXHVjNzQ0IFx1ZDU1OFx1YWUzMCBcdWM4MDRcdWFlNGNcdWM5YzAgXHVjNWJiXHVjNzQwIFx1YzgxMFx1YzIxOCBCPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgQjxzdWI+aTxcL3N1Yj4gJmxlOyAyLDAwMCwwMDAsIGkgPSAxLCAuLi4sIE4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBGN1x1Yzc0NCBcdWM2YjBcdWMyYjlcdWQ1NjAgXHVhYzAwXHViMmE1XHVjMTMxXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNzkwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRjciLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBmaWN0aW9uYWwgV29ybGQgQ2hhbXBpb25zaGlwIG9mIEZvcm11bGEgNyBEcml2ZXJzIDIwMTIgd2FzIGNoYXJhY3Rlcml6ZWQgYnkgZXhjaXRpbmcgcmFjZXMgYW5kZnJlcXVlbnQgc2hpZnRzIG9mIGRyaXZlciBwb3NpdGlvbnMgb24gdGhlIGxlYWRlcmJvYXJkLiBBbnR1biBoYXMgbWlzc2VkIG1vc3Qgb2YgaXQgYmVjYXVzZSBoZSB3YXMgdHJhaW5pbmcgZm9yIG9seW1waWFkcyBpbiBpbmZvcm1hdGljcy4gTm93IGhpcyBvbmx5IGNvbnNvbGF0aW9uIGFyZSBoaXMgbWVkYWxzIGFuZCBiZWluZyB0aGUgbWFpbiBjaGFyYWN0ZXIgaW4gdGhpcyB0YXNrLiBIZSBoYXMgYSBzaW1wbGUgcXVlc3Rpb24gZm9yIHlvdSBDT0NJIGNvbnRlc3RhbnRzOiAmYmRxdW87SG93IG1hbnkgZHJpdmVycyBwYXJ0aWNpcGF0aW5nIGluIHRoaXMgQ2hhbXBpb25zaGlwIHN0aWxsIGhhZCBhIGNoYW5jZSB0byBiZWNvbWUgRm9ybXVsYSA3IFdvcmxkIENoYW1waW9uIGF0IHRoZSBzdGFydCBvZiB0aGUgZmluYWwgcmFjZT8mcmRxdW87IFRoZSBXb3JsZCBDaGFtcGlvbiBpcywgb2YgY291cnNlLCB0aGUgZHJpdmVyIHdpdGggdGhlIGxhcmdlc3QgcG9pbnQgdG90YWwgYXQgdGhlIGVuZCAoYWZ0ZXIgdGhlIGZpbmFsIHJhY2UpLjxcL3A+XHJcblxyXG48cD5UaGVyZSBhcmUgTiBkcml2ZXJzIHBhcnRpY2lwYXRpbmcgaW4gdGhlIENoYW1waW9uc2hpcC4gVGhleSBhcmUgYWxsIGFzc2lnbmVkIHBvaW50cyBhZnRlciBlYWNoIHJhY2UsIGluY2x1ZGluZyB0aGUgZmluYWwgb25lLiBUaGUgd2lubmVyIG9mIHRoZSByYWNlIGlzIGF3YXJkZWQgTiBwb2ludHMsIHRoZSBydW5uZXItdXAgZ2V0cyBOIC0gMSBwb2ludHMsIGFuZCBzbyBvbiB1bnRpbCB0aGUgbGFzdCBkcml2ZXIsIHdobyBnZXRzIDEgcG9pbnQuIFR3byBkcml2ZXJzIGNhbm5vdCBmaW5pc2ggYSByYWNlIGluIHRoZSBzYW1lIHNwb3QuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0byBjYWxjdWxhdGUsIGJhc2VkIG9uIHRoZSB0b3RhbCBudW1iZXIgb2YgcG9pbnRzIHRoYXQgZWFjaCBkcml2ZXIgaGFzIGVhcm5lZCBiZWZvcmUgdGhlIGZpbmFsIHJhY2UsIGhvdyBtYW55IGRyaXZlcnMgc3RpbGwgaGF2ZSBhIGNoYW5jZSB0byBoYXZlIHRoZSBsYXJnZXN0IHRvdGFsIGFmdGVyIHRoZSBmaW5hbCByYWNlIGFuZCB0aHVzIHdpbiB0aGUgQ2hhbXBpb25zaGlwLiBJZiBtb3JlIHRoYW4gb25lIGRyaXZlciBoYXMgdGhlIHNhbWUgbWF4aW11bSBwb2ludCB0b3RhbCwgdGhleSBhcmUgYWxsIGF3YXJkZWQgdGhlIFdvcmxkIENoYW1waW9uIHRpdGxlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXIgTiAoMyAmbGU7IE4gJmxlOyAzMDAgMDAwKSwgdGhlIG51bWJlciBvZiBkcml2ZXJzIHBhcnRpY2lwYXRpbmcgaW4gdGhlIENoYW1waW9uc2hpcC48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBCPHN1Yj5pPFwvc3ViPiAoMCAmbGU7IEI8c3ViPmk8XC9zdWI+ICZsZTsgMiAwMDAgMDAwLCBpID0gMSwgLi4uLCBOKSwgdGhlIG51bWJlciBvZiBwb2ludHMgdGhhdCBhIGRyaXZlciBoYXMgYmVmb3JlIHRoZSBmaW5hbCByYWNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgcmVxdWVzdGVkIG51bWJlciBvZiBkcml2ZXJzIHRoYXQgY2FuIHN0aWxsIHdpbi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #1 2번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: cokcjswo
  • 잘못된 번역을 찾은 사람: kipa00