CF1420E.Battle Lemmings

A lighthouse keeper Peter commands an army of $n$ battle lemmings. He ordered his army to stand in a line and numbered the lemmings from $1$ to $n$ from left to right. Some of the lemmings hold shields. Each lemming cannot hold more than one shield.

The more protected Peter's army is, the better. To calculate the protection of the army, he finds the number of protected pairs of lemmings, that is such pairs that both lemmings in the pair don't hold a shield, but there is a lemming with a shield between them.

Now it's time to prepare for defence and increase the protection of the army. To do this, Peter can give orders. He chooses a lemming with a shield and gives him one of the two orders:

• give the shield to the left neighbor if it exists and doesn't have a shield;
• give the shield to the right neighbor if it exists and doesn't have a shield.

In one second Peter can give exactly one order.

It's not clear how much time Peter has before the defence. So he decided to determine the maximal value of army protection for each $k$ from $0$ to $\frac{n(n-1)}2$, if he gives no more that $k$ orders. Help Peter to calculate it!

灯塔看守人彼得指挥着一支由 $n$ 只战斗旅鼠组成的军队。他命令这支军队排成一列，并从左到右将旅鼠编号为 $1$ 至 $n$。其中一些旅鼠持有盾牌，且每只旅鼠最多只能持有一面盾牌。

彼得的军队受到的保护越强越好。为了计算军队的保护程度，他统计“受保护的旅鼠对”的数量：即满足如下条件的旅鼠对——该对中的两只旅鼠均未持盾，但它们之间（即在序列中位置介于二者之间）存在至少一只持盾的旅鼠。

现在到了备战时刻，需要提升军队的保护程度。为此，彼得可以下达指令：他选择一只持盾的旅鼠，并向其下达以下两种指令之一：

• 将盾牌交给左侧相邻的旅鼠（若该旅鼠存在且未持盾）；
• 将盾牌交给右侧相邻的旅鼠（若该旅鼠存在且未持盾）。

彼得每秒恰好能下达一条指令。

目前尚不清楚彼得在防御开始前还剩多少时间。因此，他决定：对每个 $k$（从 $0$ 到 $\frac{n(n-1)}{2}$），计算在至多下达 $k$ 条指令的前提下，军队保护程度所能达到的最大值。请帮助彼得完成这一计算！

First line contains a single integer $n$ ($1 \le n \le 80$), the number of lemmings in Peter's army.

Second line contains $n$ integers $a_i$ ($0 \le a_i \le 1$). If $a_i = 1$, then the $i$-th lemming has a shield, otherwise $a_i = 0$.

第一行包含一个整数 $n$（$1 \le n \le 80$），表示彼得军队中旅鼠的数量。

第二行包含 $n$ 个整数 $a_i$（$0 \le a_i \le 1$）。若 $a_i = 1$，则第 $i$ 只旅鼠持有盾牌；否则 $a_i = 0$。

Print $\frac{n(n-1)}2 + 1$ numbers, the greatest possible protection after no more than $0, 1, \dots, \frac{n(n-1)}2$ orders.

输出 $\frac{n(n-1)}2 + 1$ 个数，分别表示在最多执行 $0, 1, \dots, \frac{n(n-1)}2$ 次操作后的最大可能防护值。

Consider the first example.

The protection is initially equal to zero, because for each pair of lemmings without shields there is no lemmings with shield.

In one second Peter can order the first lemming give his shield to the right neighbor. In this case, the protection is two, as there are two protected pairs of lemmings, $(1, 3)$ and $(1, 4)$.

In two seconds Peter can act in the following way. First, he orders the fifth lemming to give a shield to the left neighbor. Then, he orders the first lemming to give a shield to the right neighbor. In this case Peter has three protected pairs of lemmings — $(1, 3)$, $(1, 5)$ and $(3, 5)$.

You can make sure that it's impossible to give orders in such a way that the protection becomes greater than three.

考虑第一个例子。

初始时保护值为 0，因为对于每一对没有盾牌的旅鼠，都不存在持有盾牌的旅鼠。

在一秒内，Peter 可以命令第一只旅鼠将其盾牌交给右侧邻居。此时保护值为 2，因为存在两对受保护的旅鼠：$(1, 3)$ 和 $(1, 4)$。

在两秒内，Peter 可以按如下方式行动：首先，他命令第五只旅鼠将其盾牌交给左侧邻居；然后，他命令第一只旅鼠将其盾牌交给右侧邻居。此时 Peter 拥有三对受保护的旅鼠——$(1, 3)$、$(1, 5)$ 和 $(3, 5)$。

你可以验证：不存在任何指令序列能使保护值超过 3。