当前没有测试数据。

E - 平均值与中位数

分数：$500$ 分

问题描述

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

高桥可以选择任意数量的卡片。然而，对于每个 $i$ $(1 \leq i \leq N - 1)$，至少必须选择 $i$ 号和 $(i+1)$ 号卡片中的其中一张。

求以下值：

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

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

约束

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

输入

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

$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$ 仍被视为正确。然而，对于中位数，必须精确输出。