102364: [AtCoder]ABC236 E - Average and Median

Problem Statement

We have $N$ cards. The $i$-th card $(1 \leq i \leq N)$ has an integer $A_i$ written on it.

Takahashi will choose any number of cards from these. However, for each $i$ $(1 \leq i \leq N - 1)$, at least one of the $i$-th and $(i+1)$-th cards must be chosen.

Find the following values.

• The maximum possible average of the integers written on the chosen cards
• The maximum possible median of the integers written on the chosen cards

Here, the median of the $n$ integers is defined to be the $\lceil \frac{n}{2} \rceil$-th smallest of them, where $\lceil x \rceil$ is the smallest integer not less than $x$.

Constraints

• $2 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^{9}$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$
$A_1$ $\ldots$ $A_N$

Output

Print two lines. The first and second lines should contain the maximum possible average and maximum possible median of the integers written on the chosen cards, respectively. For the average, your output will be considered correct when its relative or absolute error from the exact answer is at most $10^{-3}$.

Sample Input 1

6
2 1 2 1 1 10

Sample Output 1

4
2

Choosing the $2$-nd, $4$-th, and $6$-th cards makes the average of the written integers $\frac{12}{3} = 4$, which is the maximum possible.

Choosing the $1$-st, $3$-rd, $5$-th, and $6$-th cards makes the median of the written integers $2$, which is the maximum possible.

Sample Input 2

7
3 1 4 1 5 9 2

Sample Output 2

5.250000000
4

For the average, your output may contain some degree of error: for example, the output $5.2491$ is still considered correct. For the median, however, the exact value must be printed.

问题描述

我们有N张卡片。第i张卡片（1≤i≤N）上写有整数A_i。

高桥将从这些卡片中选择任意数量的卡片。但是，对于每个i（1≤i≤N-1），第i张和第（i+1）张卡片中至少要选择一张。

找出以下值。

• 所选卡片上所写整数的最大可能平均值
• 所选卡片上所写整数的最大可能中位数

这里，n个整数的中位数定义为它们中第⌈n/2⌉小的数，其中⌈x⌉表示不小于x的最小整数。

约束

• 2≤N≤10^5
• 1≤A_i≤10^{9}
• 输入中的所有值都是整数。

输入

输入格式如下：

$N$
$A_1$ $\ldots$ $A_N$

输出

打印两行。第一行和第二行分别表示所选卡片上所写整数的最大可能平均值和中位数。 对于平均值，当您的输出与精确答案之间的相对或绝对误差不超过10^{-3}时，将认为您的输出是正确的。

样例输入1

6
2 1 2 1 1 10

样例输出1

4
2

选择第2张、第4张和第6张卡片时，所写整数的平均值为$\frac{12}{3}=4$，这是最大可能的。

选择第1张、第3张、第5张和第6张卡片时，所写整数的中位数为2，这是最大可能的。

样例输入2

7
3 1 4 1 5 9 2

样例输出2

5.250000000
4

对于平均值，您的输出可能包含一定程度的误差：例如，输出5.2491仍然被认为是正确的。但对于中位数，必须打印精确值。