You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

##题目描述 有 $n$ 名战士，第 $i$ 名战士有一个武力值 $a_i$ 。

这些战士要通过进行 $n−1$ 轮决斗来决出最强的战士。如果 $i$ 和 $j$ 进行了决斗且 $a_i < a_j$ ，那么 $i$ 消失， $j$ 的武力值会变成$⌊\frac{a_i+a_j}{2}⌋$。

若两名战士武力值相同，那么编号小的会消失。

你想让最后剩下的战士武力值尽可能高。求可能的最大武力值。

##输入格式 第一行一个整数 $n$ 。 接下来一行 $n$ 个整数，表示每一个战士的武力值。 ##输出格式

一行一个整数，表示可能的最大武力值。

##样例输入

6
4 3 2 5 3 5

##样例输出

4

##样例解释 首先让武力值为 $2$ 和 $4$ 的战士决斗，则序列变为 ${3, 3, 5, 3, 5}$

让武力值为 $3$ 和 $3$ 的战士决斗，则序列变为 ${3, 5, 3, 5}$

让武力值为 $3$ 和 $5$ 的战士进行两轮决斗，则序列变为 ${4, 4}$

让最后两个战士进行决斗，则序列变为 ${4}$ 。

##数据范围 对于 $20\%$ 的数据，保证 $1 ≤ n ≤ 5$；

对于 $40\%$ 的数据，保证 $1 ≤ n ≤ 100$；

对于另外 $20\%$ 的数据，保证 $1 ≤ ai ≤ 4$；

对于 $100\%$ 的数据，保证 $1 ≤ n ≤ 100000$, $1 ≤ a_i ≤ 100000$。