史蒂夫的爬山虎农场已经满溢,到处都是爬山虎!有 $$$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$$$),说明要引爆的苦力怕的顺序。
如果有多个解决方案,您可以打印其中任何一个。
示例
输入复制
560 2 2 3 0 140 1 2 341 1 1 151 3 1 3 192 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}$$$
- $$$\次、\次、\次、\次、\次、\次$$$
在第二个测试用例中,苦力怕$$$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$$$
- $$$\次、\次、\次、\次、\次、\次、\次、\次、\次$$$