선거의 역설

Oddland에서는 민주적인 선거로 국가의 지도자를 결정한다. 국가는 홀수 개의 지역으로 나뉘며, 각 지역에는 홀수 명의 유권자가 있다.

Oddland에는 두 개의(짝수 개의!) 정당이 있으며, 가장 많은 지역에서 승리한 정당이 선거에서 승리한다. 한 정당이 어떤 지역에서 다른 정당보다 더 많은 표를 얻으면 그 지역에서 승리한다.

이 제도에서는 선거에서 패한 정당이 승리한 정당보다 더 많은 표를 얻을 수 있다. 예를 들어, 세 지역의 인구가 각각 $11$, $3$, $3$명이라면, 한 정당이 각각 $8$, $1$, $1$표를 얻고도 선거에서 패할 수 있다. 이 경우 패한 정당은 전체 인구의 과반수에 해당하는 표를 얻었다.

한 정당이 선거에서 패하면서도 얻을 수 있는 가장 많은 표의 수를 구한다.

입력의 첫째 줄에는 Oddland의 지역 수를 나타내는 홀수인 정수 $N$ ($3 \leq N \leq 999$)이 주어진다.

다음 줄에는 $N$개의 홀수인 정수 $p_i$ ($1 \leq p_i \leq 999$)이 주어지며, 이는 $N$개 도시의 인구이다.

한 정당이 선거에서 패하면서도 얻을 수 있는 가장 많은 표의 수를 출력한다.