灯塔守护者彼得指挥一支由 $$$n$$$ 战斗旅鼠组成的军队。他命令他的军队站成一排,并从左到右对旅鼠进行编号,从 $$$1$$$ 到 $$$n$$$。有些旅鼠拿着盾牌。每只旅鼠不能持有超过一个盾牌。
彼得的军队受到的保护越多越好。为了计算军队的保护力,他找到了受保护的旅鼠对的数量,即一对旅鼠中的两只旅鼠都没有持有盾牌,但其中有一只旅鼠之间有盾牌。
现在是时候做好防御准备,增加军队的防护了。为此,彼得可以发出命令。他选择了一只带盾牌的旅鼠,并给了他以下两个命令之一:
- 将盾牌交给左邻居(如果存在且没有盾牌);
- 将盾牌交给正确的邻居(如果存在且没有盾牌)。
彼得在一秒钟内可以准确地发出一个命令。
目前尚不清楚彼得在辩护之前有多少时间。因此,他决定确定从 $$$0$$$ 到 $$$\frac{n(n-1)}2$$$ 的每个 $$$k$$$ 的军队保护最大值,前提是他发出的命令不超过 $$$k$$$。帮助彼得算一下吧!
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 80$$$),即彼得军队中旅鼠的数量。
第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$0 \le a_i \le 1$$$)。如果 $$$a_i = 1$$$,则第 $$$i$$$ 个旅鼠有盾牌,否则 $$$a_i = 0$$$。
输出
打印 $$$\frac{n(n-1)}2 + 1$$$ 数字,在不超过 $$$0, 1, \dots, \frac{n(n-1)}2$$$ 订单后提供最大可能的保护。
示例
输入 #1
5 1 0 0 0 1
输出 #1
0 2 3 3 3 3 3 3 3 3 3
输入 #2
12 0 0 0 0 1 1 1 1 0 1 1 0
输出 #2
9 12 13 14 14 14 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
注意
考虑第一个例子。
保护最初等于零,因为对于每对没有盾牌的旅鼠来说,没有带有盾牌的旅鼠。
一秒钟内,彼得可以命令第一只旅鼠将他的盾牌交给右边的邻居。在这种情况下,保护是两次,因为有两对受保护的旅鼠,$$$(1, 3)$$$ 和 $$$(1, 4)$$$。
两秒钟后,Peter 可以按以下方式操作。首先,他命令第五只旅鼠给左边的邻居一个盾牌。然后,他命令第一只旅鼠给右边的邻居一个盾牌。在本例中,彼得有三对受保护的旅鼠 — $$$(1, 3)$$$、$$$(1, 5)$$$ 和 $$$(3, 5)$$$。
您可以确保不可能以保护大于三的方式发出命令。