시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (언어별 추가 시간 없음) 1024 MB 71 42 37 57.812%

문제

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

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

tncks0121은 옥토끼가 문제를 해결한 시점만 볼 수 있을 뿐, 옥토끼가 지금 문제를 풀고 있는지 쉬고 있는지 모른다. 문제 하나를 풀고 나서 다음 문제를 풀기까지 걸리는 시간이 길어지면 tncks0121의 독촉이 심해지기 때문에, 옥토끼는 이 간격의 최댓값이 최소가 되도록 계획을 세워 모든 문제를 풀려고 한다. 옥토끼를 도와 문제를 푸는 전략을 짜는 프로그램을 작성하여라. tncks0121은 통신교육이 시작되자마자 독촉을 시작하므로, 옥토끼가 첫 문제를 푸는 데 걸리는 시간도 고려해야 함에 유의하여라.

입력

첫 번째 줄에는 문제의 수 N (1 ≤ N ≤ 100,000)이 주어진다.

두 번째 줄에는 옥토끼가 각 문제를 푸는 데 걸리는 시간 Ti (1 ≤ Ti ≤ 109, Ti는 정수)가 주어진다.

출력

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

예제 입력 1

7
3 4 5 9 10 14 15

예제 출력 1

5

camp

옥토끼가 이런 식으로 문제를 풀면 tncks0121은 옥토끼가 5, 10, 15, 20, 25, 30, 34분에 문제를 풀었으므로 최대 5분동안 휴식을 한 것으로 간주한다.