题目描述

给定 $n$ 个数字 $a_1,a_2,\dots,a_n$。现在你可以选择其中若干个元素。这些元素应当满足

• 对于任意 $i\ (1\le i \le n)$ ，$a_i$ 和 $a_{i+1}$ 中至少有一个元素被选择。

现在请你求出

• 选择的元素中的最大可能的平均数
• 选择的元素中的最大可能的中位数

中位数的定义是：$k$ 个数字中第 $\lceil \frac{k}{2} \rceil$ 小的数字

输入格式

第一行一个整数 $n$

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$

输出格式

输出两行，分别代表两个问题的答案

6
2 1 2 1 1 10

4
2

7
3 1 4 1 5 9 2

5.250000000
4

数据范围

$2 \le n \le 10^5$

$1 \le a_i \le 10^9$