#88 Making a Monochrome String

Statement

길이 $N$ 의 이진 문자열 $S$ 가 주어진다. 이진 문자열이란 모든 문자가 0 또는 1인 문자열이다.

한 번의 연산으로, 현재 문자열의 비어 있지 않은 연속 부분 문자열 $T$ 중에서 $T$ 에 포함된 0의 개수와 1의 개수가 같은 것을 하나 골라 삭제할 수 있다. 삭제한 뒤에는 남은 앞부분과 뒷부분이 서로 이어 붙는다.

문자열이 단색이라는 것은 다음 중 하나를 만족한다는 뜻이다.

주어진 문자열 $S$ 를 단색으로 만들기 위해 필요한 연산 횟수의 최솟값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$N$ $S$

$S$ 를 단색으로 만들기 위해 필요한 연산 횟수의 최솟값을 출력한다.

Sample 1

Input

4
0101

Output

문자열 전체에서 0의 개수와 1의 개수가 모두 $2$ 이므로, 전체 문자열을 한 번에 삭제할 수 있다.

Sample 2

Input

5
00011

Output

앞의 0 하나를 남기고 부분 문자열 0011을 삭제하면 단색 문자열 0이 된다.

Sample 3

Input

9
100010001

Output

$3$ 번의 연산으로 단색 문자열을 만들 수 있으며, $2$ 번 이하로는 불가능하다.

Sample 4

Input

5
00000

Output

처음부터 모든 문자가 0이므로 이미 단색 문자열이다.