← 返回题目列表

Codeforces · 1367/B

B. 偶数数组

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

给定一个数组 $$$a[0 \ldots n-1]$$$,长度为 $$$n$$$,由非负整数组成。请注意,数组索引从零开始。

如果每个索引的奇偶校验与该索引处的元素的奇偶校验匹配,则该数组被称为良好数组。更正式地说,如果对于所有 $$$i$$$ ($$$0 \le i \le n - 1$$$) 等式 $$$i \bmod 2 = a[i] \bmod 2$$$ 成立,则数组是好的,其中 $$$x \bmod 2$$$ 是 $$$x$$$ 除以 2 的余数。

例如,数组 [$$$0, 5, 2, 1$$$] 和 [$$$0, 17, 0, 3$$$] 是好的,数组 [$$$2, 4, 6, 7$$$] 是坏的,因为对于 $$$i=1$$$,$$$i$$$ 和 $$$a[i]$$$ 的奇偶校验为不同:$$$i \bmod 2 = 1 \bmod 2 = 1$$$,但$$$a[i] \bmod 2 = 4 \bmod 2 = 0$$$。

在一步操作中,您可以取出数组中的任意两个元素并交换它们(这些元素不一定相邻)。

求出可以使数组 $$$a$$$ 变好的最小移动次数,或者说这是不可能的。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试中的测试用例数量。然后是 $$$t$$$ 测试用例。

每个测试用例都以包含整数 $$$n$$$ 的行开始 ($$$1 \le n \le 40$$$) — 数组 $$$a$$$ 的长度。

下一行包含 $$$n$$$ 整数 $$$a_0, a_1, \ldots, a_{n-1}$$$ ($$$0 \le a_i \le 1000$$$) - 初始数组。

输出

对于每个测试用例,输出一个整数 - 使给定数组 $$$a$$$ 良好的最小移动次数,如果不可能,则输出 -1。

示例

输入 #1

4
4
3 2 7 6
3
3 2 6
1
7
7
4 9 2 1 18 3 0

输出 #1

2
1
-1
0

注意

在第一个测试用例中,在第一次移动中,您可以交换索引为 $$$0$$$ 和 $$$1$$$ 的元素,在第二次移动中,您可以交换索引为 $$$2$$$ 和 $$$3$$$ 的元素。

在第二个测试用例中,在第一步中,您需要交换索引为 $$$0$$$ 和 $$$1$$$ 的元素。

在第三个测试用例中,您无法使数组变得良好。