题目描述

给定一个长度为 $n$ 的数组 $a$，其中每个元素均为 $-1$、$0$ 或 $1$。每次操作，你可以选择一个下标 $i$，并将 $a_i$ 加 $1$（即执行 $a_i := a_i + 1$）。你可以进行任意次数的操作，选择任意下标。

你的目标是用最少的操作次数，使得数组所有元素的乘积严格为正数，即 $a_1 \cdot a_2 \cdot \ldots \cdot a_n > 0$。求所需的最小操作次数。

保证一定可以实现目标。

输入格式

每组测试包含若干测试用例。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 8$），表示数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-1 \le a_i \le 1$），分别表示数组 $a$ 的元素。

输出格式

对于每个测试用例，输出一个整数，表示使数组所有元素的乘积严格为正所需的最小操作次数。

样例

3
3
-1 0 1
4
-1 -1 0 1
5
-1 -1 -1 0 0

3
1
4

样例说明

示例一：从 $[-1, 0, 1]$ 变为 $[1, 1, 1]$ 共需要 3 次操作。

示例二：只需将 $0$ 变为 $1$（1 次操作）。此时数组 $a=[-1,-1,1,1]$，所有元素的乘积为 $1$。

示例三：将两个 $0$ 变为 $1$（2 次操作），一个 $-1$ 变为 $1$（再需要 2 次操作），共需要 4 次操作。

由 ChatGPT 5 翻译

来源

Codeforces 2149A，英文题名 Be Positive。