题目描述

我们有 $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}$ 时，你的输出将被视为正确。

示例输入 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$ 仍然被视为正确。但是，对于中位数，必须输出精确的值。