拨动开关

密档破译了，但Echo-0的加密机关还有一个——开关。一排开关，拨动它们，改变状态。

"开关？"CC问。

"对。"你说，"$n$个开关，每个开关可以拨动。拨动一个开关会改变它和相邻开关的状态。"

"状态？"

"开或关。"你说，"用0和1表示。"

"目标？"

"给定初始状态和目标状态，求最少拨动次数。"

"咋算？"

"高斯消元。"你说，"每个开关的拨动影响一个线性方程，所有方程组成线性方程组。"

"模2？"

"对。"你说，"模2下，加法是异或——拨动两次等于没拨动。"

"自由变量？"

"对。"你说，"如果方程组有自由变量，说明多解——要枚举所有自由变量的组合，找最少拨动次数。"

"第47个开关。"你说，"$n=47$，一条直线排列。"

"能解吗？"

"能。"你说，"高斯消元$O(n^3)$，47的三次方很小。"

"答案？"

"取决于初始状态。"你说，"但总有解——因为矩阵满秩。"

"总有解？"

"对。"你说，"对于直线排列的开关问题，总有解。"

CC看着那排开关——像一排灯，像一排眼睛，像某种等待被唤醒的东西。

"拨哪个？"她问。

"看方程组的解。"你说，"解告诉你拨哪些。"

"如果我乱拨呢？"

"可能解不开。"你说，"也可能碰巧解开——但概率很小。"

"那我听你的。"

"好。"你说，"听我的。"

Echo把开关的状态投射出来——一明一暗，像呼吸，像心跳。

"以前这些开关是乱的。"她说，"现在……有顺序了。"

"因为有你教我们。"CC说。

"对。"Echo说，"因为有我。"

题目描述

$n$个开关排成一排，拨动第$i$个会改变$i-1,i,i+1$的状态。给定初始状态，求变成全关的最少拨动次数。

输入格式

第一行$n$。第二行$n$个整数表示初始状态。

输出格式

最少拨动次数。无解输出"impossible"。

输入样例

5

输出样例

1
1
1
1
1

提示

• 建立模2线性方程组，高斯消元。
• 枚举自由变量，找最少拨动次数。
• 时间复杂度$O(n^3)$或$O(2^{自由变量数})$。