합 재구성

면접 대비

시간 제한1초메모리 제한512 MB

요약

정수 목록이 주어질 때, 나머지 모든 원소의 합과 같은 원소를 하나 찾고, 없으면 BAD를 출력한다.

문제

화이트보드에서 정수 목록을 발견했다. 이 정수를 전부 사용해, 그중 하나가 나머지 전부의 합이 되는 올바른 산술식을 쓸 수 있는가?

정수는 어떤 방식으로도 바꿀 수 없다 (예: 부호를 바꾸거나 이어 붙이는 것).

첫째 줄에 화이트보드에 적힌 정수의 개수 $n$ 이 주어진다 ( $1 \le n \le 10^4$ ).

다음 $n$ 개 줄에 걸쳐 정수가 한 줄에 하나씩 주어진다. 각 정수의 절댓값은 $10^5$ 이하임이 보장된다.

입력 중 하나이면서 나머지 전부의 합인 정수 $x$ 를 하나 출력한다. 그러한 $x$ 가 여러 개면 아무거나 하나 출력한다. 그러한 $x$ 가 없으면 문자열 ‘BAD’를 출력한다.