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

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

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

입력 형식

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

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

출력 형식

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

예제 입력

7
3 4 5 9 10 14 15

예제 출력

5