solved.ac

Interview

Time limit1sMemory limit1024 MB

Summary

Given up to 300,000 difficulty votes, output the 30% trimmed mean, rounding the count trimmed at each end and the final average to the nearest integer.

Level: Easy3 of 10
Topics: Sorting, Math, Implementation
Solved: No attempts yet

Problem

solved.ac is a service built to help members of the Sogang ICPC Team study algorithms. Today, many people beyond Sogang use solved.ac to support their algorithm study.

The ICPC Team practices problem solving on an online judge, but the problems there carry no difficulty rating. Until now, it was hard to judge how difficult a problem was even when you wanted to try a range of problems, which made it difficult to decide what to solve, so solved.ac was created. Since solved.ac appeared, more than 200 contributors from around the country have shared their valuable difficulty opinions, and about 7,000 problems now carry difficulty ratings.

The difficulty of a problem is determined from the difficulty opinions submitted by the people who solved it. A difficulty opinion is a single integer meaning the difficulty the user has in mind. solved.ac determines the difficulty from the users' opinions as follows.

If there are no opinions yet, the problem's difficulty is 0.
If there is at least one opinion, the problem's difficulty is the 30% trimmed mean of all the difficulty opinions.

A trimmed mean excludes the largest and smallest values before averaging, so extreme values cannot distort the mean. For a 30% trimmed mean, 15% is removed from the top and 15% from the bottom before averaging. So if 20 people voted, the 3 votes for the highest difficulty and the 3 votes for the lowest difficulty do not count toward the mean.

The number of people removed is rounded at the top and the bottom separately. If 25 people voted, 3.75 people must be removed from each end, and here this is rounded to 4 people from each end.

Finally, the computed mean is also rounded to an integer. If the trimmed mean were 16.7, the final difficulty would be 17.

Given the list of difficulty opinions users submitted for a problem, write a program that computes the difficulty solved.ac determined.

Input

The first line gives the number of difficulty opinions n. (0 ≤ n ≤ 3 × 105)

From the second line through the 1 + n-th line, the n difficulty opinions users submitted are given one per line. Every difficulty opinion is between 1 and 30.

Output

Print the problem's difficulty as computed by solved.ac.

Examples2

Example 1
Input
```
5
1
5
5
7
8
```
Expected output
```
6
```
Example 2
Input
```
10
1
13
12
15
3
16
13
12
14
15
```
Expected output
```
13
```