给定一个数组 $$$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$$$)。
确定是否可以使数组的所有元素都等于 0。如果是,则打印导致全零状态的操作。您的解决方案不应包含超过 $$$(\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$$$。您可以按任意顺序打印它们。
示例
输入 #1
5 1 1 0 1 1
输出 #1
YES 2 1 3 5 2 3 4
输入 #2
3 0 1 0
输出 #2
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,但不可能让所有元素都等于0。