平均值与中位数

题目描述

我们有 $N$ 张卡片。第 $i$ 张卡片 $(1 \le i \le N)$ 上写有整数 $A_i$。

高桥将从中选择任意张卡片。但是，对于每个 $i$ $(1 \le i \le N - 1)$，第 $i$ 张与第 $i+1$ 张卡片中至少有一张必须被选择。

请分别求出以下两个值。

被选择的卡片上整数的平均值的最大可能值

被选择的卡片上整数的中位数的最大可能值

这里，$n$ 个整数的中位数定义为其中第 $\lceil \frac{n}{2} \rceil$ 小的数，其中 $\lceil x \rceil$ 表示不小于 $x$ 的最小整数。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出两行。第一行输出被选择卡片上整数的平均值的最大可能值，第二行输出中位数的最大可能值。 对于平均值，当你的输出与精确答案的相对误差或绝对误差不超过 $10^{-3}$ 时，判定为正确。

样例

6
2 1 2 1 1 10

4
2

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

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

7
3 1 4 1 5 9 2

5.250000000
4

对于平均值，输出允许有一定误差：例如，输出 $5.2491$ 仍然会被判定为正确。但对于中位数，必须输出精确值。

数据范围

• $2 \le N \le 10^5$
• $1 \le A_i \le 10^{9}$
• 输入中的所有值均为整数。