AT_abc453_c [ABC453C] Sneaking Glances

题目描述

高桥君位于一维数轴的坐标 $0.5$ 处。

他将进行 $N$ 次移动：

• 在第 $i$ 次移动里，他可以选择向正方向还是负方向移动，并朝选择的方向移动 $L_i$ 个单位长度。

可以任意选择第 $i$ 次的移动方向，你需要求出：高桥君穿过坐标原点（坐标 $0$ 处）的最大次数是多少。

在以上条件下，保证任何移动都不会以坐标 $0$ 为结尾。

输入格式

输入来自于标准输入，格式如下：

• 第一行输入一个整数 $N$。

• 接下来第二行 $N$ 个整数，其中第 $i$ 个整数表示 $L_i$。

输出格式

输出答案。

输入输出样例 #1

输入 #1

5
2 5 2 2 1

输出 #1

4

输入输出样例 #2

输入 #2

5
100 1 2 3 4

输出 #2

1

输入输出样例 #3

输入 #3

20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

输出 #3

20

说明/提示

【样例 $1$ 解释】

一个可行的方案如下。通过如下选择运动方向，他可以穿过坐标 $0$ 四次，这是最大的答案。

• 第一步，选择负方向并移动 $2$ 个单位长度。他从坐标 $0.5$ 移动到 $-1.5$，穿过坐标 $0$。

• 第二步，选择正向并移动 $5$。他从坐标 $-1.5$ 移动到 $3.5$，穿过坐标 $0$。

• 第三步，选择负方向并移动 $2$。他从坐标 $3.5$ 移动到 $1.5$。

• 第四步，选择负方向并移动 $2$。他从坐标 $1.5$ 移动到 $-0.5$，穿过坐标 $0$。

• 第五步，选择正向并移动 $1$。他从坐标 $-0.5$ 移动到 $0.5$，穿过坐标 $0$。

【数据范围与约束】

对于 $100\%$ 的测试数据，保证：

• $1\leq N \leq 20$

• $1\leq L_i \leq 10 ^ 9$。

• 所有输入的数据都是整数。