题目描述

你正在参加国际穿越原点大赛(International Crossing Pivot Contest, ICPC)，场上有一个数轴，开始时，你在数轴 0.5 的位置处。

你将会进行 $n$ 次移动，在第 $i$ 次移动中，你可以选择向正方向或负方向移动，距离是 $\ell_i$。

你需要最大化经过原点最大次数。

输入描述

第一行为一个整数 $n$，表示移动次数，满足 $1\leqslant n\leqslant 20$。

第二行 $n$ 个空格隔开的整数 $\ell_i$，表示每次移动的距离，满足 $1\leqslant \ell_i\leqslant 1\times 10^9$。

输出描述

求经过原点最大次数。

样例

5
2 5 2 2 1

4

5
100 1 2 3 4

1