Building Two Equal Towers

Little Ming loves to build towers with wooden blocks. He has \(N\) blocks with given heights. He wants to construct two towers such that:

• The height of a tower is the sum of the heights of the blocks used in that tower.
• Each tower must contain at least one block.
• Each block can be used at most once (and some blocks may remain unused).
• The two towers must have the same height.

Your task is to determine the maximum possible height \(H\) of the towers (each of height \(H\)) that can be built under these conditions. If it is not possible to build two towers with equal nonzero heights, output 0.

inputFormat

The first line contains an integer \(N\), the number of blocks.

The second line contains \(N\) space-separated integers denoting the heights of the blocks.

outputFormat

Output a single integer, the maximum height of the towers (each tower's height) if it is possible to build two towers with equal nonzero height, or 0 otherwise.

sample

3
1 2 3

3