中央公司的办公室拥有先进的安全系统。有 $$$10^6$$$ 员工,编号从 $$$1$$$ 到 $$$10^6$$$。
安全系统记录入口和出口。第 $$$i$$$ 员工的进入由整数 $$$i$$$ 表示,而第 $$$i$$$ 员工的离开由整数 $$$-i$$$ 表示。
公司对于进入其办公室有一些严格的规定:
- 一名员工每天最多可以进入办公室一次。
- 如果他当天不早点进入办公室,他显然无法离开办公室。
- 每天开始和结束时,办公室都是空的(员工不能过夜)。它也可能在一天中的任何时刻都是空的。
满足这些条件的任何事件数组都称为有效日。
有效或无效日期的一些示例:
- $$$[1, 7, -7, 3, -1, -3]$$$ 是有效日期($$$1$$$ 进入、$$$7$$$ 进入、$$$7$$$ 离开、$$$3$$$ 进入、$$$1$$$ 离开、$$$3$$$ 离开)。
- $$$[2, -2, 3, -3]$$$ 也是有效日期。
- $$$[2, 5, -5, 5, -5, -2]$$$ 不是有效日期,因为 $$$5$$$ 在同一天内两次进入办公室。
- $$$[-4, 4]$$$ 不是有效的一天,因为 $$$4$$$ 离开了办公室但并未在办公室。
- $$$[4]$$$ 不是有效的一天,因为 $$$4$$$ 进入了办公室并且在该天结束之前没有离开。
有 $$$n$$$ 个事件 $$$a_1、a_2、\ldots、a_n$$$(按发生顺序排列)。该数组对应于连续的一天或多天。系统管理员错误地删除了事件的日期,但他没有更改事件的顺序。
您必须将事件数组 $$$a$$$ 分区(切割)为连续的子数组,这些子数组必须表示非空的有效日期(或者说这是不可能的)。每个数组元素应该恰好属于分区的一个连续子数组。分区的每个连续子数组都应该是有效的一天。
例如,如果 $$$n=8$$$ 和 $$$a=[1, -1, 1, 2, -1, -2, 3, -3]$$$ 那么他可以将其划分为两个连续的有效日期子数组: $$$a = [1, -1~ \boldsymbol{|}~ 1, 2, -1, -2, 3, -3]$$$。
帮助管理员按要求的方式对给定数组 $$$a$$$ 进行分区,否则报告不可能这样做。找到任何需要的分区,您不应该最小化或最大化部件的数量。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^6 \le a_i \le 10^6$$$ 和 $$$a_i \neq 0$$$)。
输出
如果没有有效分区,则打印$$$-1$$$。否则,按以下格式打印任何有效分区:
- 在第一行打印 $$$d$$$ 天数 ($$$1 \le d \le n$$$)。
- 在第二行,打印 $$$d$$$ 整数 $$$c_1, c_2, \ldots, c_d$$$ ($$$1 \le c_i \le n$$$ 和 $$$c_1 + c_2 + \ldots + c_d = n$$$),其中 $$$c_i$$$ 是事件中的事件数$$$i$$$ 第一天。
如果有很多有效的解决方案,您可以打印其中任何一个。您不必最小化或最大化天数。
示例
输入 #1
6 1 7 -7 3 -1 -3
输出 #1
1 6
输入 #2
8 1 -1 1 2 -1 -2 3 -3
输出 #2
2 2 6
输入 #3
6 2 5 -5 5 -5 -2
输出 #3
-1
输入#4
3 -8 1 1
输出#4
-1
注意
在第一个示例中,整个数组都是有效日期。
在第二个示例中,一种可能的有效解决方案是将数组拆分为 $$$[1, -1]$$$ 和 $$$[1, 2, -1, -2, 3, -3]$$$($$$d = 2$$$ 和 $$$c = [2, 6]$$$)。唯一有效的解决方案是将数组拆分为 $$$[1, -1]$$$、$$$[1, 2, -1, -2]$$$ 和 $$$[3, -3]$$$ ($$$d = 3$$$ 和 $$$c = [2, 4, 2]$$$)。两种解决方案均被接受。
在第三个和第四个例子中,我们可以证明不存在有效的解。请注意,输入中给出的数组不能保证代表一组连贯的事件。