CF2229C2 We Be Flipping (Hard Version)

这是该问题的难度加强版。与其他版本的区别在于，本题中你需要最大化数组的元素和。只有在解决了所有版本后，才可以进行“hack”操作。 你有一个长度为 $n$ 的数组 $a$，数组中的元素为非零整数（可以为负数）。你最多可以进行 $n$ 次如下操作（也可以一次都不做）： - 选择一个下标 $i$（$1 \le i \le n$），要求 $a_i > 0$； - 对于每个 $j$ 满足 $1 \le j \le i$，执行 $a_j := -a_j$。 请输出一组长度不超过 $n$ 的合法操作序列，使最终数组 $a$ 的元素和最大。

每组测试数据包含多组测试用例。第一行输入测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来每组测试用例如下： 第一行输入一个整数 $n$（$2 \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$。

对于每组测试用例，输出一行整数 $k$（$0 \le k \le n$），表示你执行操作的次数。 接下来输出一行 $k$ 个整数 $b_1,\ldots,b_k$，其中 $b_i$ 表示你在第 $i$ 次操作选择的下标。 操作序列执行完后，数组 $a$ 的和应当被最大化。

在第一个测试用例中，没有可行的操作。 在第二个测试用例中，数组的和已经最大。 在第三个测试用例中，操作如下： - $[1, -3, 2, -1, 10] \xrightarrow{i = 1} [\color{red}{-1}, -3, 2, -1, 10]$ - $[-1, -3, 2, -1, 10] \xrightarrow{i = 3} [\color{red}{1, 3, -2}, -1, 10]$ 此时的数组和为 $11$，这是可以达到的最大值。 由 ChatGPT 5 翻译