C. Вставить ноль и инвертировать префикс
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть последовательность $$$a_1, a_2, \ldots, a_n$$$ длины $$$n$$$, состоящая из $$$0$$$ и $$$1$$$. Также у вас есть последовательность $$$b$$$, изначально пустая.

Вы выполните $$$n$$$ операций, каждая из которых увеличивает длину последовательности $$$b$$$ на $$$1$$$.

  • На $$$i$$$-й операции вы выбираете целое число $$$p$$$ от $$$0$$$ до $$$i-1$$$. Вы вставляете $$$0$$$ в $$$b$$$ на позицию $$$p+1$$$ (после $$$p$$$ первых элементов), после чего инвертируете $$$p$$$ первых элементов $$$b$$$.
  • Более формально: пусть перед $$$i$$$-й ($$$1 \le i \le n$$$) операцией последовательность $$$b$$$ равна $$$b_1, b_2, \ldots, b_{i-1}$$$. На $$$i$$$-й операции вы выбираете целое число $$$p$$$ от $$$0$$$ до $$$i-1$$$ и заменяете $$$b$$$ на $$$\overline{b_1}, \overline{b_2}, \ldots, \overline{b_{p}}, 0, b_{p+1}, b_{p+2}, \ldots, b_{i-1}$$$. Здесь $$$\overline{x}$$$ обозначает двоичную инверсию. Таким образом, $$$\overline{0} = 1$$$ и $$$\overline{1} = 0$$$.

Примеры применения операций приведены в примечании.

Определите, существует ли последовательность операций, после применения которой $$$b$$$ будет равна $$$a$$$. Если такая последовательность операций существует, найдите её.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют описания этих наборов.

В первой строке дано одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длина последовательности $$$a$$$.

Во второй строке даны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 1$$$) — последовательность $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных

  • выведите «NO», если невозможно сделать $$$b$$$ равной $$$a$$$ с помощью операций из условия;
  • иначе, выведите «YES» в первой строке, а во второй строке выведите $$$n$$$ чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$0 \le p_i \le i-1$$$) — описание последовательности операций, делающей $$$b$$$ равной $$$a$$$. Здесь $$$p_i$$$ должно быть равно числу, которое следует выбрать на $$$i$$$-й операции в найденной вами последовательности операций. Если существует несколько решений, выведите любое из них.
Пример
Входные данные
4
5
1 1 0 0 0
1
1
3
0 1 1
6
1 0 0 1 1 0
Выходные данные
YES
0 0 2 1 3
NO
NO
YES
0 1 0 2 4 2
Примечание

В первом наборе входных данных,

  1. Перед первой операцией, $$$b = [\,]$$$. Вы выбираете $$$p = 0$$$, после чего заменяете $$$b$$$ на $$$[\, \underline{0} \,]$$$
  2. На второй операции вы выбираете $$$p = 0$$$ и заменяете $$$b$$$ на $$$[\, \underline{0}, 0 \,]$$$.
  3. На третьей операции вы выбираете $$$p = 2$$$ и заменяете $$$b$$$ на $$$[\, 1, 1, \underline{0} \,]$$$.
  4. На четвёртой операции вы выбираете $$$p = 1$$$ и заменяете $$$b$$$ на $$$[\, 0, \underline{0}, 1, 0 \,]$$$.
  5. На пятой операции вы выбираете $$$p = 3$$$ и заменяете $$$b$$$ на $$$[\, 1, 1, 0, \underline{0}, 0 \,]$$$.

Таким образом, последовательность $$$b$$$ изменяется следующим образом: $$$[\,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0}, 0 \,]$$$ $$$\xrightarrow{p \, = \, 2}$$$ $$$[\, 1, 1, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 1}$$$ $$$[\, 0, \underline{0}, 1, 0 \,]$$$ $$$\xrightarrow{p \, = \, 3}$$$ $$$[\, 1, 1, 0, \underline{0}, 0 \,]$$$. Итоговая последовательность $$$b$$$ равна последовательности $$$a$$$, поэтому такой способ сделать операции является одним из корректных ответов.

Во втором наборе входных данных $$$n = 1$$$ и единственная последовательность $$$b$$$, которую вы можете получить, это $$$[\, 0 \, ]$$$.

В третьем наборе входных данных существует всего 6 последовательностей операций. Вот они:

  1. $$$[\,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0}, 0 \,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0}, 0, 0 \,]$$$.
  2. $$$[\,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0}, 0 \,]$$$ $$$\xrightarrow{p \, = \, 1}$$$ $$$[\, 1, \underline{0}, 0 \,]$$$.
  3. $$$[\,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0}, 0 \,]$$$ $$$\xrightarrow{p \, = \, 2}$$$ $$$[\, 1, 1, \underline{0} \,]$$$.
  4. $$$[\,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 1}$$$ $$$[\, 1, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0}, 1, 0 \,]$$$.
  5. $$$[\,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 1}$$$ $$$[\, 1, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 1}$$$ $$$[\, 0, \underline{0}, 0 \,]$$$.
  6. $$$[\,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 1}$$$ $$$[\, 1, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 2}$$$ $$$[\, 0, 1, \underline{0} \,]$$$.

Ни одна из них не делает последовательность $$$b$$$ равной $$$[\, 0, 1, 1 \,]$$$, поэтому ответ — «NO».