균형 잡힌 동물들

돈을 아끼기 위해 산타클로스는 순록 외에 다른 동물들도 단기 계약으로 썰매를 끌게 했다. 그래서 매 여행마다 썰매를 끌러 나오는 동물들의 크기가 크게 달라질 수 있다.

지난주에는 버펄로 2마리, 들쥐 37마리, 슈나우저 1마리가 있었다. 안타깝게도 버펄로 두 마리가 모두 왼쪽에 묶여 있어, 무게 불균형 때문에 비행 도중 썰매가 통째로 뒤집혔다.

앞으로 이런 사고를 막기 위해 산타는 한 여행에 나설 동물들을 두 그룹으로 나누어, 한 그룹에 속한 모든 동물의 무게 합이 다른 그룹의 무게 합과 같아지게 하려고 한다. 그리고 매다는 작업을 효율적으로 하기 위해, 산타는 정수 목표 무게 t를 찾아 t보다 가벼운 동물은 모두 한 그룹에, t보다 무거운 동물은 다른 그룹에 넣으려고 한다. 그런 t가 여러 개라면 가장 작은 것을 원한다. 문제가 하나 있다. 무게가 정확히 t인 동물이 있으면 어떻게 해야 할까? 산타는 이렇게 해결한다. 그런 동물이 짝수 마리면 두 그룹에 똑같이 나눈다(그래서 무게가 고르게 분배된다). 홀수 마리면 그중 한 마리를 요정들과 함께 장난감을 만드는 일로 보내고(어느 그룹에도 넣지 않는다), 남은 짝수 마리를 두 그룹에 똑같이 나눈다.

첫째 줄에는 정수 n (2 ≤ n ≤ 105)이 주어지며, 이는 동물의 수를 나타낸다.

다음 n개 줄에는 각각 양의 정수 w (1 ≤ w ≤ 2 ∙ 105)가 주어진다. 이는 동물들의 무게(온스)이다.

위에서 설명한 대로 가장 작은 정수 목표 무게 t를 출력한다. 그러한 정수를 찾는 것이 항상 가능함이 보장된다.