这是问题的困难版本。版本之间的唯一区别是 $$$a_i$$$ 的约束。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
Nene 正在与围成一圈的 $$$n$$$ 怪物战斗。这些怪物的编号从 $$$1$$$ 到 $$$n$$$,第 $$$i$$$ ($$$1 \le i \le n$$$) 怪物的当前能量等级为 $$$a_i$$$。
由于怪物太强大,妮妮决定使用“攻击你的邻居”法术与它们战斗。当内内使用该法术时,以下动作将按以下顺序一一发生:
- 第$$$1$$$个怪物攻击第$$$2$$$个怪物;
- 第 $$$2$$$-nd 怪物攻击 $$$3$$$-rd 怪物;
- $$$\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$$$ 使用该咒语期间会按此顺序发生以下操作:
- 内内第一次使用“攻击你的邻居”法术;
- 第$$$1$$$个怪物攻击第$$$2$$$个怪物,攻击后第$$$2$$$个怪物的能量等级等于$$$\max(0, 5-2)=3$$$;
- 第$$$2$$$-rd怪物攻击第$$$3$$$-rd怪物,攻击后第$$$3$$$-rd怪物的能量等级等于$$$\max(0, 3-3)=0$$$;
- 第$$$3$$$-st怪物攻击$$$1$$$-st怪物,攻击后$$$1$$$-st怪物的能量等级等于$$$\max(0, 2-0)=2$$$;
- 内内第二次使用“攻击你的邻居”法术;
- 第$$$1$$$个怪物攻击第$$$2$$$个怪物,攻击后第$$$2$$$个怪物的能量等级等于$$$\max(0, 3-2)=1$$$;
- 第$$$2$$$-rd怪物攻击第$$$3$$$-rd怪物,攻击后第$$$3$$$-rd怪物的能量等级等于$$$\max(0, 0-1)=0$$$;
- 第$$$3$$$-st怪物攻击$$$1$$$-st怪物,攻击后$$$1$$$-st怪物的能量等级等于$$$\max(0, 2-0)=2$$$;
- 内内第三次使用“攻击你的邻居”法术;
- 第$$$1$$$个怪物攻击第$$$2$$$个怪物,攻击后第$$$2$$$个怪物的能量等级等于$$$\max(0, 1-2)=0$$$;
- 第$$$2$$$-rd怪物攻击第$$$3$$$-rd怪物,攻击后第$$$3$$$-rd怪物的能量等级等于$$$\max(0, 0-0)=0$$$;
- 第$$$3$$$-st怪物攻击第$$$1$$$-st怪物,攻击后$$$1$$$-st怪物的能量等级等于$$$\max(0, 2-0)=2$$$。
下次每次使用该法术后,怪物的能量水平不会改变。因此,只有 $$$1$$$-st 怪物最终具有非零能量水平。
在第二个测试用例中,两个怪物最初的能量水平为零。