Reconstruct Sum

Interview

Time limit1sMemory limit512 MB

Summary

Given a list of integers, find one element that equals the sum of all the other elements, or report that none exists.

Level: Easy3 of 10
Topics: Array, Math, Hash map, Implementation
Solved: No attempts yet

Problem

On a whiteboard, you have found a list of integers. Is it possible to use all of them to write down a correct arithmetic expression where one of them is the sum of all the others?

You may not alter the integers in any way (e.g., changing the sign or concatenating).

Input

The first line of input contains an integer $n$ ( $1 \le n \le 10^4$ ), representing the number of integers on the whiteboard.

The integers on the whiteboard are given over the next $n$ lines, one per line. Their absolute values are guaranteed to be at most $10^5$ .

Output

Print a single integer $x$ which is one of the inputs, and is the sum of all the others. If there's more than one such $x$ , output any one. If there are no such values of $x$ , output the string ‘BAD’.

Examples3

Example 1
Input
```
4
1
6
3
2
```
Expected output
```
6
```
Example 2
Input
```
4
-2
0
5
-3
```
Expected output
```
0
```
Example 3
Input
```
5
1
10
4
2
-3
```
Expected output
```
BAD
```