CF2064C.Remove the Ends

你有一个长度为 $n$ 的数组 $a$，其中元素均为非零整数。初始时你有 $0$ 枚硬币，你将重复以下操作直到 $a$ 变为空：

• 设当前数组 $a$ 的大小为 $m$。选择一个整数 $i$（$1 \le i \le m$），获得 $|a_i|$ $^{\text{∗}}$ 枚硬币，然后：
  • 如果 $a_i < 0$，则将 $a$ 替换为 $[a_1,a_2,\ldots,a_{i - 1}]$（即删除从 $a_i$ 开始的后缀）；
  • 否则，将 $a$ 替换为 $[a_{i + 1},a_{i + 2},\ldots,a_m]$（即删除以 $a_i$ 结尾的前缀）。

请计算最终你能获得的最大硬币数量。

$^{\text{∗}}$ 此处 $|a_i|$ 表示 $a_i$ 的绝对值：当 $a_i > 0$ 时等于 $a_i$，当 $a_i < 0$ 时等于 $-a_i$。

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）——数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$-10^9 \le a_i \le 10^9$，$a_i \ne 0$）。

所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出最终能获得的最大硬币数量。

第一个测试用例中获得 $23$ 枚硬币的操作示例：

• $a = [3, 1, 4, -1, -5, \text{\color{red}{-9}}] \xrightarrow{i = 6} a = [3, 1, 4, -1, -5]$，获得 $9$ 枚硬币。
• $a = [\text{\color{red}{3}}, 1, 4, -1, -5] \xrightarrow{i = 1} a = [1, 4, -1, -5]$，获得 $3$ 枚硬币。
• $a = [\text{\color{red}{1}}, 4, -1, -5] \xrightarrow{i = 1} a = [4, -1, -5]$，获得 $1$ 枚硬币。
• $a = [4, -1, \text{\color{red}{-5}}] \xrightarrow{i = 3} a = [4, -1]$，获得 $5$ 枚硬币。
• $a = [4, \text{\color{red}{-1}}] \xrightarrow{i = 2} a = [4]$，获得 $1$ 枚硬币。
• $a = [\text{\color{red}{4}}] \xrightarrow{i = 1} a = []$，获得 $4$ 枚硬币。

最终共获得 $23$ 枚硬币。

第二个测试用例中获得 $40$ 枚硬币的操作示例：

• $a = [-10, -3, -17, \text{\color{red}{1}}, 19, 20] \xrightarrow{i = 4} a = [19, 20]$，获得 $1$ 枚硬币。
• $a = [\text{\color{red}{19}}, 20] \xrightarrow{i = 1} a = [20]$，获得 $19$ 枚硬币。
• $a = [\text{\color{red}{20}}] \xrightarrow{i = 1} a = []$，获得 $20$ 枚硬币。

最终共获得 $40$ 枚硬币。

翻译由 DeepSeek R1 完成