선거 역설

Oddland에서는 민주적 선거로 나라의 지도자를 뽑는다. 이 나라는 홀수 개의 지역으로 나뉘고, 각 지역에는 홀수 명의 유권자가 있다. 정당은 두 개(짝수!)이다. 승리하는 정당은 더 많은 지역에서 이긴 정당이다. 정당은 어떤 지역에서 상대 정당보다 많은 표를 받으면 그 지역을 이긴다. 이 제도에서는 패배한 정당이 승리한 정당보다 많은 표를 받는 것이 가능하다. 예를 들어 인구가 11명, 3명, 3명인 세 지역이 있을 때, 한 정당이 8표, 1표, 1표를 받고도 선거에서 질 수 있다. 이 경우 패배한 정당은 전체 인구의 과반을 얻는다. 선거에서 질 수 있는 상태에서 한 정당이 받을 수 있는 표의 최댓값을 구하시오.

첫 줄에 홀수 정수 $N$($3 \leq N \leq 999$)이 주어진다. $N$은 Oddland의 지역 수다. 다음 줄에는 $N$개의 홀수 정수 $p_i$($1 \leq p_i \leq 999$)가 주어진다. $p_i$는 $i$번째 지역의 인구다.

한 정당이 선거에서 질 수 있으면서 받을 수 있는 표의 최댓값을 출력한다.