#F0001P276. Unit Array.2A

Unit Array.2A

Unit Array

题面描述

给定一个长度为 n(1n100)n (1 \le n \le 100) 的序列 aa,所有元素均为 111-1。我们称 aa 是一个好序列,当且仅当同时满足以下两个条件:

  • a1+a2+...+an0a_1 + a_2 + ... + a_n \geq 0
  • a1a2...an=1a_1 \cdot a_2 \cdot...\cdot a_n = 1

你可以对序列进行若干次修改,每次修改可以把序列中的 1-1 改成 11 或从 11 改成 1-1

给定一个序列,问最少需要几次修改使它变成一个好的序列。

输入格式

每个测试由多个测试用例组成。第一行包含一个整数tt1t5001\le t\le 500)——测试用例的数量。测试用例的描述如下。 每个测试用例的第一行包含一个整数nn1n1001\le n\le 100)——序列aa的长度。 每个测试用例的第二行包含nn整数a1a2ana_1,a_2,\ldots,a_nai=±1a_i=\pm1)——序列aa的元素。

输出格式

对于每个测试用例,输出一个整数——使序列aa变成一个好序列所需的最小操作数。

样例 #1

样例输入 #1

7
4
-1 -1 1 -1
5
-1 -1 -1 1 1
4
-1 1 -1 1
3
-1 -1 -1
5
1 1 1 1 1
1
-1
2
-1 -1

样例输出 #1

1
1
0
3
0
1
2

提示

在第一个测试用例中,我们可以分配值 a1:=1 a_1 := 1 . 则 $ a_1 + a_2 + a_3 + a_4 = 1 + (-1) + 1 + (-1) = 0 \ge 0 $ 并且 $ a_1 \cdot a_2 \cdot a_3 \cdot a_4 = 1 \cdot (-1) \cdot 1 \cdot (-1) = 1 $。因此,我们执行了11操作。 在第二个测试用例中,我们可以分配a1:=1 a_1 := 1 . 则 $ a_1 + a_2 + a_3 + a_4 + a_5 = 1 + (-1) + (-1) + 1 + 1 = 1 \ge 0 $ 并且 $ a_1 \cdot a_2 \cdot a_3 \cdot a_4 \cdot a_5 = 1 \cdot (-1) \cdot (-1) \cdot 1 \cdot 1 = 1 $ . 。因此,我们执行了11操作。 在第三个测试用例中, $ a_1 + a_2 + a_3 + a_4 = (-1) + 1 + (-1) + 1 = 0 \ge 0 $ a $ a_1 \cdot a_2 \cdot a_3 \cdot a_4 = (-1) \cdot 1 \cdot (-1) \cdot 1 = 1 $。因此,所有条件都已满足,不需要任何操作。 在第四个测试用例中,我们可以分配值a1:=1a2:=1a3:=1a_1:=1,a_2:=1,a_3:=1。然后a1+a2+a3=1+1+1=30a_1+a_2+a_3=1+1+1=3\ge0a1a2a3=1.11=1a_1\cdot a_2\cdot a_3=1.\cdot1\cdot 1=1。因此,我们执行了33的操作。