奶牛分组

题目描述

$n$ 头奶牛按顺序排成一列，第 $i$ 头奶牛的理智度为 $a_i$。

请将所有奶牛划分为若干个小组，满足：

• 每组至少有一头奶牛，且在原队列中的位置连续。
• 每头奶牛恰好属于一个小组，不能遗漏，也不能重复分组。
• 每组奶牛的理智度之和不小于 $0$。

求最多可以分成多少组。如果不存在合法方案，输出 Impossible。

输入格式

第一行一个整数 $n$，表示奶牛数量。

接下来 $n$ 行，每行一个整数 $a_i$，按队列顺序给出每头奶牛的理智度。

输出格式

若存在合法方案，输出一个整数，表示最多可以划分的小组数。

否则输出 Impossible，注意大小写。

样例 1

5
2
-1
1
-2
3

3

样例解释

可以分为 [2]、[-1, 1]、[-2, 3]，三组的理智度之和分别为 $2,0,1$。无法划分为更多的合法小组。

样例 2

3
-2
1
0

Impossible

样例解释

所有奶牛的理智度总和为 $-1$。如果每一组的和都不小于 $0$，总和也应不小于 $0$，因此无解。

数据范围与评分

对于所有测试数据，$1\le n\le1000$，$-10^5\le a_i\le10^5$。

测试组	分值	附加限制
1	20 分	$n\le20$
2	30 分	$n\le200$
3	50 分	无

各组独立计分，组内全部测试点通过才能获得该组分数。

来源

根据洛谷 P1569「[USACO11FEB] Generic Cow Protests」整理，评分分组为本训练题配置。