有$$$n$$$扶手椅,从左到右编号为$$$1$$$到$$$n$$$。有些扶手椅有人占用(每张扶手椅最多一个人),有些则不然。占用的扶手椅数量不大于$$$\frac{n}{2}$$$。
出于某种原因,您想告诉人们从扶手椅移到其他椅子上。如果第 $$$i$$$ 个扶手椅已被某人占用,而第 $$$j$$$ 个扶手椅没有被占用,您可以告诉坐在第 $$$i$$$ 个扶手椅上的人移至第 $$$j$$$ 个扶手椅。一个人从第 $$$i$$$ 扶手椅移动到第 $$$j$$$ 扶手椅所需的时间为 $$$|i - j|$$$ 分钟。您可以多次执行此操作,但这些操作必须按顺序完成,即。 e.在您在上次操作中要求移动的人完成移动到目标扶手椅之前,您不能告诉某人移动。
您想要实现以下情况:最初占用的每个座位都必须是空闲的。您需要做的最短时间是多少?
输入
第一行包含一个整数 $$$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}$$$。
输出
打印一个整数 — 达到以下情况所需花费的最少分钟数:最初占用的每个座位都必须是空闲的。
示例
输入 #1
7 1 0 0 1 0 0 1
输出 #1
3
输入 #2
6 1 1 1 0 0 0
输出 #2
9
输入 #3
5 0 0 0 0 0
输出 #3
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$$$ 分钟。
第三次测试中,没有座位,所以你的目标立即达到。