Battle Lemmings

题意翻译

## 题目描述 有 $n$ 个守卫排成一行，编号为 $1$ 到 $n$。这些守卫里有的拿着盾牌，有的没有。**一个守卫只能同时拿一个盾牌**。 称一对守卫是被保护的，当且仅当这两个守卫都没拿盾牌，但他们之间有守卫拿了盾牌。 每一秒，指挥官可以下达两种命令中的一种，分别是： - 选一个带盾牌的守卫，把它的盾牌给他左边的守卫 - 选一个带盾牌的守卫，把它的盾牌给他右边的守卫 请求出时刻 $0$ 到 $\frac{n \times (n - 1)}{2}$ 中每个时刻最多有多少对守卫是被保护的。

题目描述

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.

输入输出样例

输入样例 #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

说明

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.

题意翻译

## 题目描述 有 $n$ 个守卫排成一行，编号为 $1$ 到 $n$。这些守卫里有的拿着盾牌，有的没有。**一个守卫只能同时拿一个盾牌**。 称一对守卫是被保护的，当且仅当这两个守卫都没拿盾牌，但他们之间有守卫拿了盾牌。 每一秒，指挥官可以下达两种命令中的一种，分别是： - 选一个带盾牌的守卫，把它的盾牌给他左边的守卫 - 选一个带盾牌的守卫，把它的盾牌给他右边的守卫 请求出时刻 $0$ 到 $\frac{n \times (n - 1)}{2}$ 中每个时刻最多有多少对守卫是被保护的。