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$ 支队伍拥有战斗力分别为 $v_i$ ，队伍在擂台上每 $1s$ 进行战斗，战斗力便会减 $1$ 。第一支出场的队伍直接成为当前的擂主，随后出场的队伍与擂主进行战斗，当其中一方的战斗力耗为零，则另一方队伍成为此时的新擂主。请你帮丛雨安排一种攻擂顺序，令前 $n$ 支队伍比赛结束后台上擂主的战斗力最小。

输入格式（match.in）

第一行一个整数 $n$ ，表示队伍数量。 第二行 $n$ 个整数，表示每支队伍的初始战斗力。

输出格式（match.out）

一行一个整数，表示最后台上擂主的最小战斗力。

输入样例

6
9 5 4 3 4 6

输出样例

1

数据范围

对 $20\%$ 的数据，满足 $v_i = 0$ 或 $1$ 。 对再 $30\%$ 的数据，满足 $v_i = i$ 。 对再 $30\%$ 的数据，满足 $n \le 15$ 。 对 $100\%$ 的数据，满足 $n \le 100, v_i \ge 0, \sum{vi}$ $≤ 10^6$ 。