You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

深入矿洞后，小 A 遇到一条需要整理的矿车传送带。传送带上依次排着 $n$ 辆矿车，第 $i$ 辆的编号是 $a_i$。

小 A 希望把所有编号为偶数的矿车都排到所有编号为奇数的矿车前面，以便红石分拣机统一处理。传送带一次只能执行一种操作：交换相邻的两辆矿车。

请你求出，最少需要多少次相邻交换，才能让所有偶数编号的矿车都出现在奇数编号的矿车前面。

例如编号为 $[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$。