题目描述

给定一个长度为 $n$ 的非零整数数组 $a$。

一次操作中，你需要选择一个当前满足 $a_i > 0$ 的下标 $i$，然后把前缀 $a_1,a_2,\ldots,a_i$ 中的所有数都乘以 $-1$。

你至多可以进行 $n$ 次操作。请输出一组合法操作，使最终数组元素和尽可能大。

这是困难版本。

输入格式

每个测试包含多组测试数据。

第一行包含整数 $t$（$1 \le t \le 10^4$）。

每组测试数据第一行包含整数 $n$（$2 \le n \le 2\cdot 10^5$），表示数组长度。

第二行包含 $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,b_2,\ldots,b_k$，其中 $b_i$ 表示第 $i$ 次操作选择的下标。

执行这些操作后，数组 $a$ 的元素和必须最大。

样例 1

5
5
-1 -2 -3 -5 -4
4
5 7 10 19
5
1 -3 2 -1 10
4
16 -13 -18 -16
11
2 -10 -11 3 -10 15 7 18 16 17 -9

0

0

2
1 3
0

6
6 3 1 5 4 7

约束与提示

• 时间限制：2 秒

• 内存限制：256 MB

• 原题编号：CF2229C2