Score : $500$ points

问题描述

我们有 $N$ 张卡片。第 $i$ 张卡片（$1 \leq i \leq N$）上写有一个整数 $A_i$。

Takahashi 将从这些卡片中选择任意数量的卡片。但是，对于每个 $i$ （$1 \leq i \leq N - 1$），至少需要选择第 $i$ 张和第 $(i+1)$ 张卡片中的其中一张。

找出以下两个值：

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

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

以上为通义千问 qwen-max 翻译，仅供参考。

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