P12688 [KOI 2022 Round 1] 避开

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

有一个长度为 $N$ 的数组 $A = [A_1, A_2, \cdots, A_N]$，其中所有元素都是非负整数。你可以对数组 $A$ 执行任意次数的操作，每次操作可以交换相邻的两个数。 你的目标是使数组中「奇数与偶数相邻的情况最多只出现一次」。请计算达到这一目标所需的最小交换次数。 请注意，$0$ 也视作偶数。 例如，考虑数组 $A = [4, 5, 1, 0]$。如果先交换最后两个元素，再交换中间两个元素，数组将变为 $[4, 0, 5, 1]$。此时，奇数与偶数相邻的情况只出现了一次，满足条件。 

第一行输入整数 $N$。 第二行输入 $N$ 个整数，表示数组 $A$ 的各个元素，按顺序以空格分隔。

输出一行，表示最少需要多少次操作，才能使奇数与偶数相邻的情况最多只出现一次。

**约束条件** - $1 \leq N \leq 1\,000\,000$ - $0 \leq A_i \leq 2 \times 10^9$，其中 $1 \leq i \leq N$ - 所有 $A_i$ 为整数 **子任务** 1. （10 分）$N \leq 3$ 2. （40 分）$N \leq 1\,000$ 3. （50 分）无附加约束条件