옥토끼는 통신교육을 풀어라!!

옥토끼는 UCPC World Finals 2020을 준비하며 여름학교에 가기 위해 통신교육 문제를 푼다. 그러나 악덕 조교 tncks0121은 옥토끼가 오랫동안 문제를 풀지 않으면 '옥통풀'을 외치며 독촉한다.

옥토끼는 $N$개의 문제를 모두 풀어야 하며, 각 문제를 푸는 데 $T_i$분이 걸린다. 옥토끼는 멀티태스킹 능력이 있어 한 번에 두 개의 문제를 동시에 풀 수 있다. 모든 문제는 정수 시각에 풀기 시작해야 하며, 한 번 풀기 시작한 문제는 도중에 중단하지 않는다. 옥토끼가 항상 문제를 풀고 있을 필요는 없으며, 문제를 푸는 순서에는 제약이 없다.

tncks0121은 옥토끼가 문제를 해결한 시점만 볼 수 있을 뿐, 지금 문제를 풀고 있는지 쉬고 있는지는 알 수 없다. 문제 하나를 풀고 나서 다음 문제를 풀기까지 걸리는 시간이 길수록 독촉이 심해지므로, 옥토끼는 이 간격의 최댓값이 최소가 되도록 계획을 세워 모든 문제를 풀려고 한다. tncks0121은 통신교육이 시작되자마자 독촉을 시작하므로, 옥토끼가 첫 문제를 푸는 데 걸리는 시간도 고려해야 한다.

첫 번째 줄에 문제의 수 $N$ ($1 \le N \le 100000$)이 주어진다.

두 번째 줄에는 옥토끼가 각 문제를 푸는 데 걸리는 시간 $T_i$ ($1 \le T_i \le 10^9$, $T_i$는 정수)가 주어진다.

첫 번째 줄에 옥토끼가 문제 하나를 풀고 나서 다음 문제를 풀기까지 걸리는 최대 시간의 최솟값을 출력한다.