题目描述

有一个长度为 $N$ 的数组 $A = [A_1, A_2, \cdots, A_N]$，其中所有元素都是非负整数。你可以对数组 $A$ 执行任意次数的操作，每次操作可以交换相邻的两个数。

你的目标是使数组中「奇数与偶数相邻的情况最多只出现一次」。请计算达到这一目标所需的最小交换次数。

请注意，$0$ 也视作偶数。

例如，考虑数组 $A = [4, 5, 1, 0]$。如果先交换最后两个元素，再交换中间两个元素，数组将变为 $[4, 0, 5, 1]$。此时，奇数与偶数相邻的情况只出现了一次，满足条件。

输入格式

第一行输入整数 $N$。

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

输出格式

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

1
1

0

4
4 5 1 0

2

4
1 2 3 1

1

提示

约束条件

• $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 分）无附加约束条件