Inverse Range Sort

問題

ご近所の川を訪ねると、そこには二種類の石がちゃっかりと並べられていました。佳純ちゃんはこれを見て、番号の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

Problem Description

Visiting a local river awaited Kasumi a series of two kinds of rocks aligned carefully. She would like to sort it so that rocks that look like a digit 1 would sit contiguously.

One operation involves a selection of a range consisting of an equal number of both kinds to swap them together. What is the minimum number of operation to achieve her mission?

Constraints

• $4\leq N\leq 2\times10^5$
• $\{0, 1\}\in S$

Input Example 1

7 1001011

Output Example 1

2

This is feasible by undergoing following transitions: (1001011)->(0110011)->(0111100)