P1569 Generic Cow Protests（通俗版）

题目大意

有 (n) 头奶牛排成一列，第 (i) 头奶牛的"理智度"为 (a_i)（可以是正也可以是负）。

现在要把这 (n) 头奶牛按顺序切成若干个连续的小组，要求每个小组内所有奶牛的理智度之和都不小于 0。请你计算：最多能切成多少个小组？ 如果无论怎么切都做不到（也就是不存在任何满足条件的切法），输出 Impossible。

连续的小组指的是在原队列中一段接一段，中间不能跳着选。

输入格式

• 第一行：一个整数 (n) —— 奶牛的数量。
• 接下来 (n) 行：第 (i+1) 行给出一个整数 (a_i) —— 第 (i) 头奶牛的理智度。

输出格式

• 若存在合法切法，输出一个整数：可以分成的小组最大数量；
• 否则输出 Impossible。

样例

输入

4
2
3
-3
1

输出

3

解释：一种最优切法是

• 第 1 组：([2])，和为 2；
• 第 2 组：([3,-3])，和为 0；
• 第 3 组：([1])，和为 1。 共 3 组，且每组和都不小于 0。

说明 / 数据范围

• 对于 30% 的数据：(\(1 \le n \le 20\))。
• 对于 100% 的数据：(\(1 \le n \le 1000\))，(\(|a_i| \le 10^5\))。