Score : $500$ points

问题描述

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

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

以上为kimi 翻译，仅供参考。

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.

update @ 2024/3/10 10:14:03