选择
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

给你一个长度为n的只包含正整数的数组a,你需要选择数组中至少一个元素,你的得分是你所选元素的中位数加上你所选元素的数量。你能找到你能获得的最大得分吗?

定义长度为n的数组的中位数是将该数组按非递减顺序排序后下标为\lfloor \frac{n+1}2 \rfloor的元素,其中\lfloor \rfloor符号表示向下取整,例如数组[2, 2, 5, 3, 7]的中位数为3,数组[7,2,6,4]的中位数为4

输入描述:

1行给定一个整数n(1\le n\le 5 \times {10}^3),表示数组的长度。

2行包含n个整数a_1, a_2, \ldots, a_n (1 \le a_i \le 10^9),表示数组元素,两个整数之间用空格隔开。

输出描述:

输出一行整数,表示你能获得的最大得分。
示例1

输入

复制
4
3 6 7 8

输出

复制
10