题目描述

给定一个包含 $n$ 个数字的序列，现在你可以执行任意次以下操作：

• 选定两个相邻的数字，并交换它们的位置。

问，最少需要交换多少次，才可以使得序列中没有相同奇偶性的数字相邻。（换句话说，序列需要呈奇偶数字交错的形式。）

输入格式

第一行包含一个整数 $t$，代表测试样例的组数。 ($1 \le t \le 10^4$)

对于每组测试样例：

第一行输入一个正整数 $n$$(1 \le n \le 10^5)$

第二行输入 $n$ 个整数 $a_i$，$1 \le a_i \le 1000$。

保证在一个测试点中，$n$ 的总和不超过 $10^5$。

输出格式

对于每个测试样例，输出需要的最少操作次数。

如果不可能把数组变成要求的形式，输出 -1。

5
3
6 6 1
1
9
6
1 1 1 2 2 2
2
8 6
6
6 2 3 4 5 1

1
0
3
-1
2

提示

在第一个测试用例中，以下操作序列将满足要求：

1. swap(2, 3)。执行操作后的数组： $[6, 1, 6]$

在第二个测试用例中，数组最初不包含两个具有相同奇偶性的相邻项。

在第三个测试用例中，以下操作序列将满足要求：

1. swap(3, 4)。执行操作后的数组： $[1, 1, 2, 1, 2, 2]$
2. swap(2, 3)。执行操作后的数组： $[1, 2, 1, 1, 2, 2]$
3. swap(4, 5)。执行操作后的数组： $[1, 2, 1, 2, 1, 2]$

在第四个测试用例中，无法满足要求。

在第五个测试用例中，以下操作序列将满足要求：

1. swap(2, 3)。执行操作后的数组： $[6, 3, 2, 4, 5, 1]$
2. swap(4, 5)。执行操作后的数组： $[6, 3, 2, 5, 4, 1]$