虚式ソート

問題

ご近所の川を訪ねると、そこには二種類の石がちゃっかりと並べられていました。佳ちゃんはこれを見て、番号の1のような見た目をした石が隣接するよう並び替えたいと思い付きます。

一回の操作では、二種類の石が同数含まれている区間を一つ選択し、その範囲内の石の種類を反転します。佳ちゃんは、最小で何回の操作を必要としますか？

制約

• $2\leq N\leq 16$
• $\{0, 1\}\in S$

入力形式

N
S

入力例1

7 
1001011

出力例1

2

以下の遷移を辿ることで達成可能です。($1001011$)->($0110011$)->($0111100$)

入力例2

14
11010001000011

出力例2

4

入力例3

4
0101

出力例3

1

入力例4

12
111110000010

出力例4

1

入力例5

16
1010101010101010

出力例5

7

入力例6

7
1110111

出力例6

3