题目描述

小 Z 有一个字符串 $S$，字符串只包含三种数字字符 0,1,2。

现在给出一个定义：一个字符串是优雅的，当且仅当没有相邻的两个字符是相同的。

• 例如，字符串 01220 不是优雅的，因为有两个相邻的 2，字符串 01020102120 是优雅的。

小 Z 每一次可以交换字符串 $S$ 中任意一对相邻的字符，问把字符串 $S$ 变成优雅的的至少需要操作几次？如果字符串 $S$ 原本就是优雅的，则输出 0。

输入格式

从 string.in 文件读入数据。

输入一行一个字符串 $S$，其中只包含三种字符 0,1,2。

输出格式

输出到 string.out 文件。

输出一行一个整数，表示最少操作次数。如果不需要操作，则输出 0，如果无解输出 -1。

样例

00122

2

0101020002

-1

000201202

6

0000120202010210211110212202020222222200000111111000001112222000012120102012010201200

55

说明/提示

样例 1 解释

交换 $(S_2,S_3)$，结果为 01022。

交换 $(S_3,S_4)$，结果为 01202。

数据范围

对于 $30\%$ 的数据，$1 \leq |S| \leq 12$。

对于另外 $30\%$ 的数据，$S$ 中 $0$ 的个数大于 $\lfloor \frac{|S|}{2} \rfloor$。

对于 $100\%$ 的数据，$1 \leq |S| \leq 400$。