F. Огниво
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ферма криперов Стива переполнена, поэтому криперы спавнятся повсюду! Есть $$$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
Примечание

В первом наборе входных данных последовательность взрывов выглядит следующим образом:

  • $$$\underline{0, \mathbf{2}, 2}, 3, 0, 1$$$
  • $$$\times, \underline{\times, \times, \mathbf{3}, 0, 1}$$$
  • $$$\times, \times, \times, \times, \times, \times$$$
где $$$\times$$$ представляет мертвого крипера. Обратите внимание, что если бы Стив сначала взорвал крипера $$$4$$$, единственным оставшимся в живых был бы крипер $$$1$$$, которого нельзя взорвать.

Во втором наборе входных данных крипер $$$1$$$ не может быть взорван, и ни один из криперов $$$2$$$, $$$3$$$ или $$$4$$$ не имеет достаточной взрывной силы, чтобы его убить, поэтому решения нет.

В пятом наборе входных данных последовательность взрывов выглядит следующим образом:

  • $$$\underline{\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$$$
  • $$$\times, \times, \times, \times, \times, \times, \times, \times, \times$$$