这是该问题的困难版本。两个版本之间的唯一区别在于 $a_i$ 的数据范围。只有在两个版本的问题都解决的情况下，你才可以进行 hack。
Nene 正在与 $n$ 只围成一圈的怪物战斗。这些怪物编号从 $1$ 到 $n$，第 $i$ 只（$1 \le i \le n$）怪物的当前能量值为 $a_i$。
由于怪物太强了，Nene 决定使用“攻击邻居”法术来对付它们。当 Nene 使用此法术时，会按以下顺序依次发生以下动作：
- 第 $1$ 只怪物攻击第 $2$ 只怪物；
- 第 $2$ 只怪物攻击第 $3$ 只怪物；
- ...
- 第 $(n-1)$ 只怪物攻击第 $n$ 只怪物；
- 第 $n$ 只怪物攻击第 $1$ 只怪物。
当能量值为 $x$ 的怪物攻击能量值为 $y$ 的怪物时，被攻击怪物的能量值变为 $\max(0, y-x)$（攻击怪物的能量值保持为 $x$ 不变）。
Nene 打算使用该法术 $10^{100}$ 次，并亲自处理剩余能量值不为零的怪物。她希望你确定在使用了 $10^{100}$ 次该法术后，哪些怪物的能量值仍不为零。
输入格式
每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。接下来是测试用例的描述。
每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$) —— 怪物的数量。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) —— 怪物的当前能量值。
保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。
输出格式
对于每个测试用例：
- 第一行输出一个整数 $m$ —— 在使用 $10^{100}$ 次法术后，能量值不为零的怪物的数量；
- 第二行输出 $m$ 个整数 $i_1, i_2, \ldots, i_m$ ($1 \le i_1 < i_2 < \ldots < i_m \le n$) —— 这些怪物按编号递增顺序排列的索引。
如果 $m=0$，你可以输出一个空行，也可以不输出。
样例
输入 1
5 3 2 5 3 2 0 0 4 1 5 7 2 4 4 2 1 2 13 1 1 4 5 1 4 1 9 1 9 8 1 0
输出 1
1 1 0 1 1 2 1 3 6 1 3 6 8 10 12
说明
在第一个测试用例中，前 $3$ 次使用法术期间按顺序发生以下动作：
- Nene 第一次使用“攻击邻居”法术；
- 第 $1$ 只怪物攻击第 $2$ 只怪物，攻击后第 $2$ 只怪物的能量值变为 $\max(0, 5-2)=3$；
- 第 $2$ 只怪物攻击第 $3$ 只怪物，攻击后第 $3$ 只怪物的能量值变为 $\max(0, 3-3)=0$；
- 第 $3$ 只怪物攻击第 $1$ 只怪物，攻击后第 $1$ 只怪物的能量值变为 $\max(0, 2-0)=2$；
- Nene 第二次使用“攻击邻居”法术；
- 第 $1$ 只怪物攻击第 $2$ 只怪物，攻击后第 $2$ 只怪物的能量值变为 $\max(0, 3-2)=1$；
- 第 $2$ 只怪物攻击第 $3$ 只怪物，攻击后第 $3$ 只怪物的能量值变为 $\max(0, 0-1)=0$；
- 第 $3$ 只怪物攻击第 $1$ 只怪物，攻击后第 $1$ 只怪物的能量值变为 $\max(0, 2-0)=2$；
- Nene 第三次使用“攻击邻居”法术；
- 第 $1$ 只怪物攻击第 $2$ 只怪物，攻击后第 $2$ 只怪物的能量值变为 $\max(0, 1-2)=0$；
- 第 $2$ 只怪物攻击第 $3$ 只怪物，攻击后第 $3$ 只怪物的能量值变为 $\max(0, 0-0)=0$；
- 第 $3$ 只怪物攻击第 $1$ 只怪物，攻击后第 $1$ 只怪物的能量值变为 $\max(0, 2-0)=2$。
在接下来的每次法术使用后，怪物的能量值不再改变。因此，最终只有第 $1$ 只怪物拥有非零能量值。
在第二个测试用例中，两只怪物最初的能量值均为零。