Okto Rabbit Solves the Correspondence Course!!

Okto Rabbit is preparing for UCPC World Finals 2020 and solves correspondence course problems to get into a summer school. However, the strict teaching assistant tncks0121 shouts '옥통풀' to press him whenever he has not solved a problem for a long time.

Rabbit must solve all $N$ problems, and solving problem $i$ takes $T_i$ minutes. He has strong multitasking ability, so he can solve two problems at the same time. Every problem must start at an integer time, and once a problem is started, it cannot be stopped partway. Rabbit does not have to be solving a problem at all times, and there is no constraint on the order in which the problems are solved.

tncks0121 can only see the moments when Rabbit finishes a problem. He cannot tell whether Rabbit is solving a problem or resting. The longer the gap between finishing one problem and finishing the next, the harder he presses, so Rabbit wants a plan that minimizes the largest such gap while solving all problems. tncks0121 starts pressing as soon as the course begins, so the time Rabbit takes to solve the first problem must also be counted.

The first line contains the number of problems $N$ ($1 \le N \le 100000$).

The second line contains $T_i$ ($1 \le T_i \le 10^9$, $T_i$ is an integer), the number of minutes needed to solve each problem.

Print on the first line the minimum possible value of the largest time that passes between finishing one problem and finishing the next.