A13841 | 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!

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$ .

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.