#P0043. 非负积一数列

非负积一数列

题目描述

给定一个长度为 nn 的数列 {a}\{a\} ,其中的每个元素都是 −1-1 或 11 。如果同时满足以下条件,我们就把这个数列 {a}\{a\} 称为非负积一数列:

  • a1+a2+…+an≥0a_1 + a_2 + \ldots + a_n \ge 0 ;

  • a1⋅a2⋅…⋅an=1a_1 \cdot a_2 \cdot \ldots \cdot a_n = 1 .

每次操作,您可以选择数列 {a}\{a\} 中的任意元素,并为它乘以 −1-1。换句话说,如果 ai=−1a_i = -1 ,则可以将改为 11 ;如果 ai=1a_i = 1 ,则可以将改为 −1-1。

确定使数列 {a}\{a\} 变为非负积一数列所需的最少操作数。可以证明这总是可能的。

输入格式

输入的第一行包含一个整数 nn ( 1≤n≤1071 \le n \le 10^7 ) - 数组 aa 的中元素的个数。

每个测试用例的第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n ( ai=±1a_i = \pm 1 ) - 数组 aa 的元素。

输出格式

输出一行一个整数,即要使数列 {a}\{a\} 变为非负积一数列所需的最少操作数。

样例 #1

样例输入 #1

4
-1 -1 1 -1

样例输出 #1

1

样例 #2

样例输入 #2

5
-1 -1 -1 1 1

样例输出 #2

1

样例 #3

样例输入 #3

3
-1 -1 -1

样例输出 #3

3