← 返回题目列表

Codeforces · 1556/B

B. 就位!

中文机器翻译题面 查看原题

William 有一个 $$$n$$$ 整数数组 $$$a_1, a_2, \dots, a_n$$$。他一步就能交换两个相邻的物品。如果条件 $$$|i - j| ,则两个项目 $$$a_i$$$ 和 $$$a_j$$$ 被视为相邻项= 1$$$ 满意。

William 希望您计算他需要执行的最小交换次数,以使数组不包含具有相同奇偶校验的两个相邻项。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ $$$(1 \le n \le 10^5)$$$,它是 William 数组中的项目总数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$,它们是 William 的数组。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出所需的最少操作数,或者如果不可能使数组达到没有相邻数字具有相同奇偶校验的状态,则输出 $$$-1$$$。

示例

输入 #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

1
0
3
-1
2

注意

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

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

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

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

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

在第四个测试用例中,不可能满足要求。

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

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