Description

Xiao Ming likes stacking blocks. He currently has $N$ wooden blocks. He wants to build two towers of equal height. The height of a tower is the sum of the heights of all blocks used to build it, and each tower must use at least one block. Each block can be used at most once, and it is allowed to leave some blocks unused. Given the height of each block, determine the maximum possible height of the towers when the two towers have the same height. Can you help him?

Input Format

The first line contains an integer $N$, the number of blocks. The second line contains $N$ integers, the heights of the $N$ blocks.

Output Format

Output a single integer, the maximum height of the towers that can be built. If it is impossible to build two towers of the same height, output -1.

3
2 3 5

5

Hint

Constraints: For 100% of the testdata, $N \le 50$. Each block height $h$ satisfies $1 \le h \le 500000$, and the total sum of all block heights is $\le 500000$.

Translated by ChatGPT 5