311253: CF1956E1. Nene vs. Monsters (Easy Version)

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

This is the easy 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 2 \cdot 10^5$) — 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.

题目大意：
这是一个名为 "E1. Nene vs. Monsters (Easy Version)" 的编程问题。题目描述了Nene与n个怪物进行战斗的情景，这些怪物排成一个圆形。每个怪物有一个能量值a_i。Nene使用一个名为 "Attack Your Neighbour" 的咒语，按照顺序使每个怪物攻击其相邻的怪物。当一个怪物攻击另一个怪物时，被攻击的怪物的能量值会减少攻击怪物的能量值，但不会小于0。Nene将使用这个咒语10^100次，然后亲自处理那些能量值非零的怪物。需要确定在使用这个咒语10^100次后，哪些怪物的能量值会是非零的。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。
- 每个测试用例包含两行：
- 第一行包含一个整数n（2 ≤ n ≤ 2 * 10^5），表示怪物的数量。
- 第二行包含n个整数a_1, a_2, ..., a_n（0 ≤ a_i ≤ 2 * 10^5），表示每个怪物的初始能量值。

输出：
- 对于每个测试用例：
- 第一行输出一个整数m，表示在使用咒语10^100次后能量值非零的怪物数量。
- 第二行输出m个整数i_1, i_2, ..., i_m（1 ≤ i_1 < i_2 < ... < i_m ≤ n），表示这些怪物的编号。
- 如果m=0，可以输出一个空行或者不输出。

公式（LaTeX格式）：
当怪物x攻击怪物y时，怪物y的能量值变为：
\[ y' = \max(0, y - x) \]
其中，x是攻击者的能量值，y是被攻击者的能量值，y'是被攻击后的能量值。题目大意： 这是一个名为 "E1. Nene vs. Monsters (Easy Version)" 的编程问题。题目描述了Nene与n个怪物进行战斗的情景，这些怪物排成一个圆形。每个怪物有一个能量值a_i。Nene使用一个名为 "Attack Your Neighbour" 的咒语，按照顺序使每个怪物攻击其相邻的怪物。当一个怪物攻击另一个怪物时，被攻击的怪物的能量值会减少攻击怪物的能量值，但不会小于0。Nene将使用这个咒语10^100次，然后亲自处理那些能量值非零的怪物。需要确定在使用这个咒语10^100次后，哪些怪物的能量值会是非零的。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。 - 每个测试用例包含两行： - 第一行包含一个整数n（2 ≤ n ≤ 2 * 10^5），表示怪物的数量。 - 第二行包含n个整数a_1, a_2, ..., a_n（0 ≤ a_i ≤ 2 * 10^5），表示每个怪物的初始能量值。 输出： - 对于每个测试用例： - 第一行输出一个整数m，表示在使用咒语10^100次后能量值非零的怪物数量。 - 第二行输出m个整数i_1, i_2, ..., i_m（1 ≤ i_1 < i_2 < ... < i_m ≤ n），表示这些怪物的编号。 - 如果m=0，可以输出一个空行或者不输出。 公式（LaTeX格式）： 当怪物x攻击怪物y时，怪物y的能量值变为： \[ y' = \max(0, y - x) \] 其中，x是攻击者的能量值，y是被攻击者的能量值，y'是被攻击后的能量值。