Two Representative Natural Numbers

Given several positive integers, choose representative positive integers by two different criteria.

Criterion 1 chooses a positive integer that minimizes the sum of absolute differences from all given numbers. For the numbers 4, 3, 2, 2, 10, 10, choosing 3 gives |4-3| + |3-3| + |2-3| + |2-3| + |10-3| + |10-3| = 17, and choosing 4 also gives 17. Since this is the minimum possible value, the representatives by criterion 1 are 3 and 4. If there is more than one representative, choose the smallest one.

Criterion 2 chooses a positive integer that minimizes the sum of squared differences from all given numbers. For the same numbers, choosing 5 gives (4-5)^2 + (3-5)^2 + (2-5)^2 + (2-5)^2 + (10-5)^2 + (10-5)^2 = 73, which is the minimum possible value.

For the given positive integers, find the representative positive integer for criterion 1 and for criterion 2. A representative does not have to be one of the input numbers.

The first line contains the number of positive integers N. N is between 1 and 5,000,000, inclusive.

The second line contains N positive integers separated by spaces. Each integer is between 1 and 10,000, inclusive.

Print two integers on the first line: the representative for criterion 1 and the representative for criterion 2, separated by a space.

If a criterion has two or more possible representatives, print the smallest one among them.