스카우트

Johnny의 보이스카우트 팀은 지휘 체계를 바꾸려 한다. 팀에는 1번부터 $n$번까지 번호가 붙은 대원 $n$명이 있다. 지휘 체계는 다음과 같이 정의된다.

• 지휘 체계에는 지휘관이 한 명 있다.
• 번호가 지휘관보다 작은 대원들이 첫 번째 하위 팀을, 번호가 지휘관보다 큰 대원들이 두 번째 하위 팀을 이룬다. 하위 팀 중 하나 또는 둘 모두 비어 있을 수 있다.
• 비어 있지 않은 하위 팀은 각자 자신의 지휘 체계를 갖는다.
• 팀의 지휘관은 하위 팀들의 지휘관을 감독한다.

메시지는 외부에서 대원 한 명에게 전달된다. 메시지를 받은 대원은 읽은 뒤 자신의 상급자에게 넘긴다. 이 과정은 메시지가 팀 전체의 지휘관에게 도달할 때까지 반복된다. $i$번 대원이 메시지를 읽는 데 $a_i$의 시간이 걸린다. 메시지 처리 시간은 메시지를 넘겨받은 모든 대원(팀 전체 지휘관 포함)의 읽기 시간을 합한 값이다.

메시지를 처음 받는 대원은 누구인지 알 수 없다. 따라서 Johnny는 가능한 최대 처리 시간이 가장 작아지도록 지휘 체계를 다시 짜야 한다. 그 최솟값을 구하라.

첫째 줄에 대원의 수 $n$ ($1 \le n \le 2\,000$)이 주어진다.

둘째 줄에는 각 대원이 메시지를 읽는 데 걸리는 시간 $a_i$ ($1 \le a_i \le 1\,000\,000\,000$)가 공백으로 구분되어 $n$개 주어진다.

가능한 최대 처리 시간의 최솟값을 정수 하나로 출력한다.

첫 번째 예제에서 최적의 지휘 체계는 아래 그림의 왼쪽과 같다. 정점 안의 숫자는 해당 대원의 읽기 시간이다. 메시지의 최대 처리 시간은 13이다.

두 번째 예제에서 최적의 지휘 체계는 위 그림의 오른쪽과 같다. 최대 처리 시간은 4이다.