← 返回题目列表

Codeforces · 2133/F

F. 打火石

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

史蒂夫的爬山虎农场已经满溢,到处都是爬山虎!有 $$$n$$$ 苦力怕站成一排,第 $$$i$$$ 个苦力怕具有爆炸力 $$$e_i$$$。史蒂夫需要杀死所有人才能通过。

为此,他可以使用他值得信赖的打火石 引爆 爬行者。引爆位置 $$$i$$$ 的苦力怕会杀死位置 $$$j$$$ 的所有苦力怕,这样 $$$|i - j| \lt e_i$$$。死去的苦力怕无法被引爆。有些苦力怕可能特别弱并且具有爆炸力 $$$0$$$,这意味着它们也无法被引爆。

大猪紧追不舍,没有时间可以浪费了。找到一系列爆炸,以尽可能少的爆炸杀死所有苦力怕,或者报告这是不可能的。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$) — 苦力怕的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$e_1, e_2,\ldots, e_n$$$ ($$$0 \le e_i \le n$$$) - 每个苦力怕的爆炸力。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。

输出

对于每个测试用例,如果不可能杀死所有苦力怕,则输出 $$$-1$$$。

否则,输出两行。在第一行,输出一个整数 $$$k$$$ ($$$1 \leq k \leq n$$$),即所需的最小爆炸次数。然后输出一行 $$$k$$$ 整数 $$$d_1, d_2, \ldots, d_k$$$ ($$$1 \leq d_i \leq n$$$),说明要引爆的苦力怕的顺序。

如果有多个解决方案,您可以打印其中任何一个。

示例

输入
复制

5
6
0 2 2 3 0 1
4
0 1 2 3
4
1 1 1 1
5
1 3 1 3 1
9
2 0 2 4 2 2 4 1 1

输出
复制

2
2 4
-1
4
2 4 1 3
2
2 5
3
1 7 3

注意

在第一个测试用例中,爆炸顺序如下:

  • $$$\下划线{0, \mathbf{2}, 2}, 3, 0, 1$$$
  • $$$\times, \underline{\times, \times, \mathbf{3}, 0, 1}$$$
  • $$$\次、\次、\次、\次、\次、\次$$$
其中 $$$\times$$$ 代表死亡的苦力怕。请注意,如果史蒂夫首先引爆了苦力怕 $$$4$$$,那么唯一活着的苦力怕将是无法被引爆的苦力怕 $$$1$$$。

在第二个测试用例中,苦力怕$$$1$$$无法被引爆,并且苦力怕$$$2$$$、$$$3$$$或$$$4$$$都没有足够高的爆炸力来杀死它,所以没有解决方案。

在第五个测试用例中,爆炸顺序如下:

  • $$$\下划线{\mathbf{2}, 0}, 2, 4, 2, 2, 4, 1, 1$$$
  • $$$\times, \times, 2, \underline{4, 2, 2, \mathbf{4}, 1, 1}$$$
  • $$$\times、\underline{\times、\mathbf{2}、\times}、\times、\times、\times、\times、\times$$$
  • $$$\次、\次、\次、\次、\次、\次、\次、\次、\次$$$