题目描述

小 D 有一个包含 $n$ 个正整数的数组。他希望把数组中的偶数全部移到奇数前面，且只能使用"交换相邻两个元素"这一种操作。

小 D 想知道，最少需要进行多少次交换，才能让所有偶数出现在所有奇数的前面？

例如数组 $[3, 5, 2, 4, 1]$，最少需要 $4$ 次相邻交换：

• $2$ 先和 $5$ 交换 → $[3, 2, 5, 4, 1]$
• $2$ 再和 $3$ 交换 → $[2, 3, 5, 4, 1]$
• $4$ 和 $5$ 交换 → $[2, 3, 4, 5, 1]$
• $4$ 和 $3$ 交换 → $[2, 4, 3, 5, 1]$

共 $4$ 次交换后，所有偶数已排在奇数前面，满足要求。

输入格式

第一行一个整数 $n$，表示数组长度。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示数组元素。

输出格式

一行一个整数，表示最少需要的相邻交换次数。

样例

5
3 5 2 4 1

4

3
1 2 3

1

3
2 4 6

0

4
1 3 5 7

0

样例解释

• 样例 $1$：见题目描述。
• 样例 $2$：数组 $[1, 2, 3]$，$2$ 是偶数，需要和前面的 $1$ 交换一次 → $[2, 1, 3]$，满足要求。共 $1$ 次。
• 样例 $3$：全部已是偶数，已在奇数前面，不需要交换。
• 样例 $4$：全部是奇数，同样不需要交换。

数据范围与约定

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le a_i \le 10^6$。