这是该问题的简单版本。两个版本之间唯一的区别是对 $a_i$ 的限制。只有当两个版本都被解决时,你才能进行 Hack。
Nene 正在与围成一圈的 $n$ 个怪物战斗。这些怪物的编号为 $1$ 到 $n$,第 $i$($1 \le i \le n$)个怪物当前的能量值为 $a_i$。
由于怪物们太强大了,Nene 决定使用“攻击你的邻居”(Attack Your Neighbour)法术来与它们战斗。当 Nene 使用这个法术时,以下事件将依次发生:
- 第 $1$ 个怪物攻击第 $2$ 个怪物;
- 第 $2$ 个怪物攻击第 $3$ 个怪物;
- ……
- 第 $(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 2 \cdot 10^5$)—— 怪物们当前的能量值。
保证所有测试用例中 $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$ 个怪物拥有非零的能量值。
在第二个测试用例中,两个怪物初始的能量值都为零。