题目描述

$n$ 个数 $a_{1}\dots a_n$ 排成一列。现在要选出一些数，满足 任意两个相邻的数中至少有一个数被选择。

请求出：

• 所有选择方案中，被选中的数字平均值的最大值，误差在 $10^{-3}$ 以内视为正确；
• 所有选择方案中，被选中的数字中位数的的最大值。在这里，偶数 $2k$ 个数的中位数视作第 $k$ 小的数。

输入格式

第一行输入一个整数 $n$ 。

第二行输入 $n$ 个整数 $a_1,...,a_n$ 。

输出格式

输出两行。

第一行输出所有选择方案中，被选中的数字平均值的最大值，误差在 $10^{-6}$ 以内视为正确。

第二行输出所有选择方案中，被选中的数字中位数的的最大值。

样例 #1

样例输入 #1

6
2 1 2 1 1 10

样例输出 #1

4
2

选第二、第四、第六个数，平均值最大

选第一、第三、第五、第六个数，中位数最大

样例 #2

样例输入 #2

7
3 1 4 1 5 9 2

样例输出 #2

5.250000000
4

数据范围

$2\ \leq\ N\ \leq\ 10^5 , 1\ \leq\ A_i\ \leq\ 10^{9}$