← 返回题目列表

Codeforces · 1956/E1

E1. Nene vs. Monsters (简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。版本之间的唯一区别是 $$$a_i$$$ 的约束。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

Nene 正在与围成一圈的 $$$n$$$ 怪物战斗。这些怪物的编号从 $$$1$$$ 到 $$$n$$$,第 $$$i$$$ ($$$1 \le i \le n$$$) 怪物的当前能量等级为 $$$a_i$$$。

由于怪物太强大,妮妮决定使用“攻击你的邻居”法术与它们战斗。当内内使用该法术时,以下动作将按以下顺序一一发生:

- 第$$$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 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$$$ 使用该咒语期间会发生以下操作(按此顺序):

- 内内第一次使用“攻击你的邻居”法术;
- 第$$$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 怪物最终具有非零能量水平。

在第二个测试用例中,两个怪物最初的能量水平为零。