E. Тройное инвертирование
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ длины $$$n$$$, состоящий из нулей и единиц.

Можно несколько раз выполнить следующую операцию, состоящую из двух шагов:

  1. Взять произвольные целые числа $$$1 \le x < y < z \le n$$$, образующие арифметическую прогрессию ($$$y - x = z - y$$$).
  2. Поменять значения $$$a_x, a_y, a_z$$$ на противоположные (т.е. $$$1$$$ заменить на $$$0$$$, $$$0$$$ заменить на $$$1$$$).

Определите, возможно ли обнулить все элементы массива. Если возможно, то выведите сами операции, причём их количество не должно превышать $$$(\lfloor \frac{n}{3} \rfloor + 12)$$$. Здесь $$$\lfloor q \rfloor$$$ означает число $$$q$$$, округленное вниз. Можно показать, что если можно обнулить все элементы массива, то можно их обнулить и не более чем за такое количество операций.

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

Первая строка содержит одно целое число $$$n$$$ ($$$3 \le n \le 10^5$$$) — длина массива.

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

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

В первой строке выведите «YES» (без кавычек), если ответ существует, и «NO» (без кавычек) иначе. Вы можете выводить каждую букву в любом регистре (строчную или заглавную).

Если ответ существует, то во второй строке выведите целое число $$$m$$$ ($$$0 \le m \le (\lfloor \frac{n}{3} \rfloor + 12)$$$) — количество операций в ответе.

Далее в ($$$i + 2$$$)-й строке выведите $$$i$$$-ю операцию — числа $$$x_i, y_i, z_i$$$. Допустимо выводить эти три числа в произвольном порядке.

Примеры
Входные данные
5
1 1 0 1 1
Выходные данные
YES
2
1 3 5
2 3 4
Входные данные
3
0 1 0
Выходные данные
NO
Примечание

Изменения массива в первом тесте в авторском решении:

  • 1 1 0 1 1 (начальное состояние)
  • 0 1 1 1 0 (поменялись значения у первого, третьего и пятого элемента)
  • 0 0 0 0 0 (поменялись значения у второго, третьего и четвёртого элемента)

Возможны и другие ответы. В этом тесте количество операций не должно превышать $$$\lfloor \frac{5}{3} \rfloor + 12 = 1 + 12 = 13$$$.

Во втором тесте единственная доступная операция — это поменять значения всех элементов на противоположные. Следовательно, можно получить массивы 0 1 0 и 1 0 1, но нельзя обнулить все элементы.