CF2260D Signs of Prefix Sums

给定一个整数数组 $a_1, a_2, \dots, a_n$，其中没有元素等于 $0$，定义前缀和数组 $p_1, p_2, \dots, p_n$，其中 $p_i$ 等于数组 $a$ 的前 $i$ 个元素的和。 根据前缀和数组，可以构造一个长度为 $n$ 的字符串 $s$：如果 $p_i > 0$，则 $s$ 的第 $i$ 个字符为 +；如果 $p_i < 0$，则第 $i$ 个字符为 -；如果 $p_i = 0$，则第 $i$ 个字符为 0。 例如，对于数组 $a=[2, -1, -1, -2, 2]$，其前缀和为 $p = [2, 1, 0, -2, 0]$，因此对应的字符串为 ++0-0。 数组 $a$ 的代价定义为 $\max\limits_{1 \le i \le n} |a_i|$。 现在给定一个字符串 $s$，求能够构造出该字符串的整数数组 $a$ 的最小可能代价。数组 $a$ 的所有元素必须非零。如果不存在这样一个数组，输出 $-1$。

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——表示测试用例数。 每个测试用例包括两行。第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）——字符串 $s$ 的长度。第二行包含一个由字符 0、+、- 组成的长度为 $n$ 的字符串 $s$。 输入数据还满足所有测试用例中 $n$ 的和不超过 $3 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示数组 $a$ 的最小可能代价。如果不存在符合要求的数组，输出 $-1$。

示例中各测试用例的最优数组 $a$： 1. $[1]$； 2. 不存在符合要求的数组； 3. $[2, -1, -1]$； 4. $[1, -3, 1, 2]$； 5. $[1, -2, -1, 1, 2]$； 6. $[2, -2, 2, -1, -2]$。 由 ChatGPT 5 翻译