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

В ряд стоят $$$n$$$ кресел, пронумерованных от $$$1$$$ до $$$n$$$ слева направо. Некоторые кресла заняты людьми (не более одного человека на кресло), остальные свободны. Количество занятых мест не превосходит $$$\frac{n}{2}$$$.

По некоторым причинам вы хотите пересадить людей. Если $$$i$$$-е кресло занято, а $$$j$$$-е — нет, вы можете попросить человека, сидящего в $$$i$$$-м кресле, пересесть в $$$j$$$-е кресло. Время, которое потребуется на перемещение из $$$i$$$-го кресла в $$$j$$$-е, равно $$$|i - j|$$$ минутам. Эту операцию можно проводить любое количество раз, но операции должны выполняться последовательно, то есть вы не можете попросить человека пересесть, пока человек, которого вы попросили в предыдущей операции, еще не закончил перемещение.

Вы бы хотели добиться следующей ситуации: все кресла, которые были заняты в самом начале, должны оказаться свободными. За какое минимальное время вы сможете это сделать?

Входные данные

В первой строке задано одно целое число $$$n$$$ ($$$2 \le n \le 5000$$$) — количество кресел.

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 1$$$). $$$a_i = 1$$$ означает, что $$$i$$$-е кресло изначально занято, $$$a_i = 0$$$ означает, что это кресло свободно. Количество занятых кресел не превосходит $$$\frac{n}{2}$$$.

Выходные данные

Выведите одно целое число — минимальное количество минут, за которое вы можете добиться следующей ситуации: все кресла, которые были заняты в самом начале, должны оказаться свободными.

Примеры
Входные данные
7
1 0 0 1 0 0 1
Выходные данные
3
Входные данные
6
1 1 1 0 0 0
Выходные данные
9
Входные данные
5
0 0 0 0 0
Выходные данные
0
Примечание

В первом примере возможна следующая последовательность действий:

  1. попросить человека пересесть из кресла $$$1$$$ в кресло $$$2$$$ за $$$1$$$ минуту;
  2. попросить человека пересесть из кресла $$$7$$$ в кресло $$$6$$$ за $$$1$$$ минуту;
  3. попросить человека пересесть из кресла $$$4$$$ в кресло $$$5$$$ за $$$1$$$ минуту.

Во втором примере возможна следующая последовательность действий:

  1. попросить человека пересесть из кресла $$$1$$$ в кресло $$$4$$$ за $$$3$$$ минуты;
  2. попросить человека пересесть из кресла $$$2$$$ в кресло $$$6$$$ за $$$4$$$ минуты;
  3. попросить человека пересесть из кресла $$$4$$$ в кресло $$$5$$$ за $$$1$$$ минуту;
  4. попросить человека пересесть из кресла $$$3$$$ в кресло $$$4$$$ за $$$1$$$ минуту.

В третьем примере ни одно место не занято, поэтому вам не надо тратить время.