#88 Making a Monochrome String

Statement

Statement language

You are given a binary string $S$ of length $N$ . A binary string is a string whose every character is either $\texttt{0}$ or $\texttt{1}$ .

In one operation, you may choose a non-empty contiguous substring $T$ of the current string such that the number of $\texttt{0}$ s in $T$ is equal to the number of $\texttt{1}$ s in $T$ , and delete it. After deletion, the remaining prefix and suffix are concatenated.

A string is called monochrome if it satisfies one of the following conditions.

The string is empty.
Every character of the string is $\texttt{0}$ .
Every character of the string is $\texttt{1}$ .

Find the minimum number of operations required to make $S$ monochrome.

Input

The input is given in the following format.

$N$ $S$

Output

Print the minimum number of operations required to make $S$ monochrome.

Constraints

$1 \le N \le 200\,000$ .
$S$ is a binary string of length $N$ .

Subtasks

#	Score	Constraints
1	20	$N \le 20$ .
2	30	$N \le 5\,000$ .
3	50	No additional constraints.

Samples

Sample 1

Input

4
0101

Output

Since the number of 0s and 1s in the entire string are both $2$ , the entire string can be deleted at once.

Sample 2

Input

5
00011

Output

Leaving the first 0 and deleting the substring 0011 results in the monochromatic string 0.

Sample 3

Input

9
100010001

Output

A monochromatic string can be made with $3$ operations, and it can be proven that is it the optimal answer.

Sample 4

Input

5
00000

Output

All characters are 0 from the beginning, so it is already a monochromatic string.