时间限制： 1.0 秒

空间限制： 256 MB

题目描述

给定一个长度为 $n$ 的仅由 $0$ 和 $1$ 组成的整数序列，每次操作可以将一个任意位置的 $1$ 与一个任意位置的 $0$ 交换，问使序列中所有 $1$ 都在连续区间的最少操作次数。

输入格式

从标准输入读入数据。

第一行为一个正整数 $n$，表示正整数序列长度。

第二行为 $n$ 个整数 $a_i$，表示整数序列。

输出格式

输出到标准输出。

输出一个整数，表示最少操作次数。

5
1 0 1 0 1

1

样例 1 解释

将第二个元素 0 与第五个元素 1 交换，可以得到新序列 1 1 1 0 0，此时所有的 1 处于连续区间，因此最少操作次数为 $1$。

3
0 1 0

0

样例 2 解释

由于序列中只有一个 1，因此所有的 1 已经处于连续区间，最少操作次数为 $0$。

8
1 0 0 1 1 0 0 1

2

样例 3 解释

1. 将第一个元素 1 与第三个元素 0 交换，可以得到新序列 0 0 1 1 1 0 1；
2. 再将第六个元素 0 与第八个元素 1 交换，可以得到新序列 0 0 1 1 1 1 0 0。

此时所有的 1 处于连续区间，因此最少操作次数为 $2$。

子任务

对于所有数据，保证 $1\le n\le 10^5,~a_i\in\{0,1\}$。

来源

2022 浙江大学计算机考研机试模拟赛 T2 - 晴问