Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

E. Боевые лемминги
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Смотритель маяка Петр командует отрядом из $$$n$$$ боевых леммингов. Он выстроил свою армию в шеренгу и пронумеровал леммингов целыми числами от $$$1$$$ до $$$n$$$ слева направо. Некоторые из леммингов держат щиты, причем каждый лемминг не может держать более одного щита.

Чем более защищенными будут войска Петра, тем лучше. Чтобы вычислить защищенность отряда, он вычисляет количество защищенных пар леммингов, т. е. таких, что они оба не держат щиты, а между ними стоит хотя бы один лемминг со щитом.

Сейчас необходимо подготовиться к обороне и увеличить защиту войск. Для этого Петр может отдавать приказы. Он может выбрать лемминга со щитом и отдать ему один из двух приказов:

  • передать щит соседу слева, если такой существует, и у него еще нет щита;
  • передать щит соседу справа, если такой существует, и у него еще нет щита.
За одну секунду Петр отдает ровно один приказ.

Пока неизвестно, как скоро придется обороняться. Поэтому Петр хочет для каждого $$$k$$$ от $$$0$$$ до $$$\frac{n(n-1)}2$$$ определить максимально возможную защищенность армии, если он отдаст не более $$$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$$$ приказов.

Примеры
Входные данные
5
1 0 0 0 1
Выходные данные
0 2 3 3 3 3 3 3 3 3 3
Входные данные
12
0 0 0 0 1 1 1 1 0 1 1 0
Выходные данные
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)$$$.

За две секунды Петр может поступить следующим образом: сначала приказать пятому леммингу передать щит соседу слева, а затем — первому леммингу передать щит соседу справа. Тогда найдется три защищенные пары — $$$(1, 3)$$$, $$$(1, 5)$$$ и $$$(3, 5)$$$.

Можно убедиться, что защищенности лучше, чем три, добиться никак нельзя.