You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有 $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$ 分钟。

在第三个样例中，没有椅子被占用，因此目标已经达成，所需时间为 $0$。