Vasya 和 Petya 发明了一种新游戏。 Vasya 采用由 1 × n 方格组成的条纹,并将方格涂成黑色和白色。之后,Petya 可以开始移动——在移动过程中,他可以选择任意两个相邻的一种颜色的方块,并以他想要的方式重新绘制这两个方块,也许可以用不同的颜色。 Petya 只能将方块重新绘制为白色和黑色。佩蒂亚的目标是重新绘制条纹,这样相邻的两个方块就不会是同一种颜色。帮助 Petya,使用给定的初始颜色,找到 Petya 获胜所需的最少步数。
输入
第一行包含数字 n (1 ≤ n ≤ 1000),表示条带的长度。第二行恰好包含 n 个符号——该行的初始颜色。 0 对应白色方块,1 对应黑色方块。
输出
如果 Petya 无法通过这样的初始着色获胜,则打印 -1。否则打印 Petya 获胜所需的最小步数。
示例
输入 #1
6 111010
输出 #1
1
输入 #2
5 10001
输出 #2
1
输入 #3
7 1100010
输出 #3
2
输入#4
5 00100
输出#4
2
注意
在第一个示例中,Petya 可以选取方格 1 和 2。他将方格 1 重新绘制为黑色,将方格 2 重新绘制为白色。
在第二个示例中,Petya 可以选取方格 2 和 3。他将方格 2 重新绘制为白色,将方格 3 重新绘制为黑色。