DMOPC '17 Contest 3 P1 - An Early Christmas Present

View as PDF

Submit solution


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 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 to 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
-10^6 \le A_i \le 10^6

Subtask 2 [90%]

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

Input Specification

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

Output Specification

A single integer, the mark that when removed, maximizes the average of the remaining 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

1

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