这是本题的困难版本。两个版本之间唯一的区别是 $a_i$ 的数据范围。只有当两个版本都解决时，你才能进行 Hack。

Nene 正在与围成一圈的 $n$ 只怪物战斗。这些怪物从 $1$ 到 $n$ 编号，第 $i$（$1 \le i \le n$）只怪物当前的能量值为 $a_i$。

由于怪物太强大了，Nene 决定使用“攻击你的邻居”（Attack Your Neighbour）法术来与它们战斗。当 Nene 使用该法术时，会依次发生以下事件：

• 第 $1$ 只怪物攻击第 $2$ 只怪物；
• 第 $2$ 只怪物攻击第 $3$ 只怪物；
• $\ldots$
• 第 $(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$ 只怪物拥有非零的能量值。

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