CF1956E2 Nene vs. Monsters (Hard Version)

这是该问题的困难版本。两个版本的唯一区别在于 $a_i$ 的约束条件。只有当你同时解决了两个版本的问题时，才能进行 Hack。 Nene 正在与 $n$ 个怪物战斗，这些怪物围成一个圆圈。这些怪物从 $1$ 到 $n$ 编号，第 $i$ 个怪物（$1 \le i \le n$）当前的能量值为 $a_i$。 由于怪物们太强大，Nene 决定使用“攻击你的邻居”法术与它们战斗。当 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$，你可以输出一个空行，也可以不输出这一行。

在第一个测试用例中，前 $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$ 个怪物的能量值不为零。 在第二个测试用例中，两个怪物的初始能量值都为零。 由 ChatGPT 4.1 翻译