В ряд стоят \(n\) кресел, пронумерованных от \(1\) до \(n\) слева направо. Некоторые кресла заняты людьми (не более одного человека на кресло), остальные свободны. Количество занятых мест не превосходит \(\frac{n}{2}\).
По некоторым причинам вы хотите пересадить людей. Если \(i\)-е кресло занято, а \(j\)-е — нет, вы можете попросить человека, сидящего в \(i\)-м кресле, пересесть в \(j\)-е кресло. Время, которое потребуется на перемещение из \(i\)-го кресла в \(j\)-е, равно \(|i - j|\) минутам. Эту операцию можно проводить любое количество раз, но операции должны выполняться последовательно, то есть вы не можете попросить человека пересесть, пока человек, которого вы попросили в предыдущей операции, еще не закончил перемещение.
Вы бы хотели добиться следующей ситуации: все кресла, которые были заняты в самом начале, должны оказаться свободными. За какое минимальное время вы сможете это сделать?
Выходные данные
Выведите одно целое число — минимальное количество минут, за которое вы можете добиться следующей ситуации: все кресла, которые были заняты в самом начале, должны оказаться свободными.
Примечание
В первом примере возможна следующая последовательность действий:
- попросить человека пересесть из кресла \(1\) в кресло \(2\) за \(1\) минуту;
- попросить человека пересесть из кресла \(7\) в кресло \(6\) за \(1\) минуту;
- попросить человека пересесть из кресла \(4\) в кресло \(5\) за \(1\) минуту.
Во втором примере возможна следующая последовательность действий:
- попросить человека пересесть из кресла \(1\) в кресло \(4\) за \(3\) минуты;
- попросить человека пересесть из кресла \(2\) в кресло \(6\) за \(4\) минуты;
- попросить человека пересесть из кресла \(4\) в кресло \(5\) за \(1\) минуту;
- попросить человека пересесть из кресла \(3\) в кресло \(4\) за \(1\) минуту.
В третьем примере ни одно место не занято, поэтому вам не надо тратить время.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1 0 0 1 0 0 1
|
3
|
|
2
|
6
1 1 1 0 0 0
|
9
|
|
3
|
5
0 0 0 0 0
|
0
|