这是该问题的困难版本。两个版本之间的唯一区别在于 $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$ 只怪物拥有非零能量值。

在第二个测试用例中，两只怪物最初的能量值均为零。