DMOPC '17 Contest 3 P1 - An Early Christmas Present

Points: 3 (partial)

Time limit: 2.0s

Memory limit: 64M

Author:

Problem type

Your teacher has decided to give you an early Christmas present: they will drop one of your $N$ ~N~ test marks! Being a very academically focused student, you naturally want your resulting average of the remaining marks to be as high as possible. As a student at the prestigious DMCI: Modern Computing Institute, your marks do not simply range from $0$ ~0~ to $100$ ~100~, but have a much larger range. Which mark should you drop to maximize your average?

Constraints

Subtask 1 [10%]

$2 \le N \le 1\,000$ ~2 \le N \le 1\,000~
$-10^6 \le A_i \le 10^6$ ~-10^6 \le A_i \le 10^6~

Subtask 2 [90%]

$2 \le N \le 10^5$ ~2 \le N \le 10^5~
$-10^9 \le A_i \le 10^9$ ~-10^9 \le A_i \le 10^9~

Input Specification

The first line of input will contain a single integer: $N$ ~N~.
The next line will contain $N$ ~N~ space-separated integers: $A_1, A_2, \dots, A_N$ ~A_1, A_2, \dots, A_N~, the $i^\text{th}$ ~i^\text{th}~ of which corresponds to your $i^\text{th}$ ~i^\text{th}~ mark.

Output Specification

A single integer, the mark that when removed, maximizes the average of the remaining $N-1$ ~N-1~ marks.

Sample Input 1

5
98 -20 96 100 96

Sample Output 1

-20

Sample Input 2

4
3 3 1 1

Sample Output 2

Comments

9

felixzhang25 commented on April 15, 2018, 4:38 p.m. ← edited →

Sample Input 1

5

98 -20 96 100 96

lOL hOW diD yOU GEt -20 oN a tESt