311254: CF1956E2. Nene vs. Monsters (Hard Version)

E2. Nene vs. Monsters (Hard Version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is the hard version of the problem. The only difference between the versions is the constraints on $a_i$. You can make hacks only if both versions of the problem are solved.

Nene is fighting with $n$ monsters, located in a circle. These monsters are numbered from $1$ to $n$, and the $i$-th ($1 \le i \le n$) monster's current energy level is $a_i$.

Since the monsters are too strong, Nene decided to fight with them using the Attack Your Neighbour spell. When Nene uses this spell, the following actions happen in the following order one by one:

• The $1$-st monster attacks the $2$-nd monster;
• The $2$-nd monster attacks the $3$-rd monster;
• $\ldots$
• The $(n-1)$-th monster attacks the $n$-th monster;
• The $n$-th monster attacks the $1$-st monster.

When the monster with energy level $x$ attacks the monster with the energy level $y$, the energy level of the defending monster becomes $\max(0, y-x)$ (the energy level of the attacking monster remains equal to $x$).

Nene is going to use this spell $10^{100}$ times and deal with the monsters that will still have a non-zero energy level herself. She wants you to determine which monsters will have a non-zero energy level once she will use the described spell $10^{100}$ times.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of test cases follows.

The first line contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of monsters.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — the current energy levels of monsters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case,

• in the first line output an integer $m$ — the number of monsters with non-zero energy level after $10^{100}$ uses of the spell;
• in the second line of output $m$ integers $i_1,i_2,\ldots,i_m$ ($1 \le i_1 < i_2 < \ldots < i_m \le n$) — the indices of these monsters in the increasing order.

If $m=0$, you may either output an empty line or don't output it.

ExampleInput

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

Output

1
1 
0

1
1 
2
1 3 
6
1 3 6 8 10 12 

Note

In the first test case, the following actions happen during the first $3$ uses of the spell in this order:

• Nene uses the Attack Your Neighbour spell for the first time;
• the $1$-st monster attacks the $2$-nd monster, after the attack the energy level of the $2$-nd monster becomes equal to $\max(0, 5-2)=3$;
• the $2$-nd monster attacks the $3$-rd monster, after the attack the energy level of the $3$-rd monster becomes equal to $\max(0, 3-3)=0$;
• the $3$-rd monster attacks the $1$-st monster, after the attack the energy level of the $1$-st monster becomes equal to $\max(0, 2-0)=2$;
• Nene uses the Attack Your Neighbour spell for the second time;
• the $1$-st monster attacks the $2$-nd monster, after the attack the energy level of the $2$-nd monster becomes equal to $\max(0, 3-2)=1$;
• the $2$-nd monster attacks the $3$-rd monster, after the attack the energy level of the $3$-rd monster becomes equal to $\max(0, 0-1)=0$;
• the $3$-rd monster attacks the $1$-st monster, after the attack the energy level of the $1$-st monster becomes equal to $\max(0, 2-0)=2$;
• Nene uses the Attack Your Neighbour spell for the third time;
• the $1$-st monster attacks the $2$-nd monster, after the attack the energy level of the $2$-nd monster becomes equal to $\max(0, 1-2)=0$;
• the $2$-nd monster attacks the $3$-rd monster, after the attack the energy level of the $3$-rd monster becomes equal to $\max(0, 0-0)=0$;
• the $3$-rd monster attacks the $1$-st monster, after the attack the energy level of the $1$-st monster becomes equal to $\max(0, 2-0)=2$.

After each of the next uses of the spell, energy levels of monsters do not change. Thus, only the $1$-st monster has a non-zero energy level in the end.

In the second test case, both monsters initially have zero energy level.

题目大意：
这个题目是“Nene vs. Monsters”的困难版本。唯一的不同是对于$a_i$的限制。只有当两个版本的问题都解决时，你才能进行hack。

Nene正在和一个圆环上的$n$个怪物战斗。这些怪物从1到$n$编号，第$i$个（$1 \le i \le n$）怪物的当前能量水平是$a_i$。

由于怪物太强大，Nene决定使用“Attack Your Neighbour”咒语来对付它们。当Nene使用这个咒语时，以下行动按以下顺序一个接一个地发生：
1. 第1个怪物攻击第2个怪物；
2. 第2个怪物攻击第3个怪物；
3. ...
4. 第$n-1$个怪物攻击第$n$个怪物；
5. 第$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$。

输出：
对于每个测试用例，
1. 在第一行输出一个整数$m$——在使用咒语$10^{100}$次后具有非零能量水平的怪物数量；
2. 在第二行输出$m$个整数$i_1, i_2, \ldots, i_m$（$1 \le i_1 < i_2 < \ldots < i_m \le n$）——这些怪物的索引，按递增顺序。

如果$m=0$，你可以选择输出一个空行或者不输出。

示例输入输出：
输入：
```
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
0

1
1
2
1 3
6
1 3 6 8 10 12
```题目大意： 这个题目是“Nene vs. Monsters”的困难版本。唯一的不同是对于$a_i$的限制。只有当两个版本的问题都解决时，你才能进行hack。 Nene正在和一个圆环上的$n$个怪物战斗。这些怪物从1到$n$编号，第$i$个（$1 \le i \le n$）怪物的当前能量水平是$a_i$。 由于怪物太强大，Nene决定使用“Attack Your Neighbour”咒语来对付它们。当Nene使用这个咒语时，以下行动按以下顺序一个接一个地发生： 1. 第1个怪物攻击第2个怪物； 2. 第2个怪物攻击第3个怪物； 3. ... 4. 第$n-1$个怪物攻击第$n$个怪物； 5. 第$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$。 输出： 对于每个测试用例， 1. 在第一行输出一个整数$m$——在使用咒语$10^{100}$次后具有非零能量水平的怪物数量； 2. 在第二行输出$m$个整数$i_1, i_2, \ldots, i_m$（$1 \le i_1 < i_2 < \ldots < i_m \le n$）——这些怪物的索引，按递增顺序。 如果$m=0$，你可以选择输出一个空行或者不输出。 示例输入输出： 输入： ``` 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 0 1 1 2 1 3 6 1 3 6 8 10 12 ```