대비 강의

안테와 고란이 프로그래밍 대회를 앞둔 $N$개 팀을 지도한다. 두 사람은 각자 설명할 알고리즘을 하나씩 맡고 있어서, 모든 팀은 안테의 강의와 고란의 강의를 각각 한 번씩 들어야 한다.

$i$번 팀이 알고리즘 하나를 이해하고 구현하는 데 $t_i$의 시간이 걸리며, 이 시간은 두 강의에서 똑같다. 강의는 중간에 끊지 않고 진행한다. 안테와 고란은 같은 팀을 같은 시각에 가르치지 못하고, 한 사람이 두 팀을 같은 시각에 가르치지도 못한다. 두 사람은 언제든 쉴 수 있고, 팀은 두 강의를 어느 순서로 들어도 된다.

두 사람이 강의를 모두 끝내는 데 걸리는 최소 시간을 구하시오.

첫째 줄에 팀의 수 $N$이 주어진다.

둘째 줄에 $N$개의 정수 $t_1, t_2, \dots, t_N$이 공백으로 구분되어 주어진다. $t_i$는 $i$번 팀이 알고리즘 하나를 이해하고 구현하는 데 걸리는 시간이다.

입력의 모든 수는 $[1, 3 \times 10^5]$ 구간에 속한다.

최소 시간을 정수 하나로 출력한다.

첫 번째 예제에서는 모든 팀이 2의 시간을 쓴다. 안테가 1번 팀, 2번 팀, 3번 팀을 차례로 가르치고 고란이 3번 팀, 1번 팀, 2번 팀을 차례로 가르치면 된다.

두 번째 예제에서는 안테가 2번 팀과 3번 팀을 차례로 가르친 뒤 1의 시간만큼 쉬고 1번 팀을 가르치고, 고란이 1번 팀, 3번 팀, 2번 팀을 차례로 가르치면 된다.