#156 빨강과 파랑

Loading problem...

Preparing the statement, recent submissions, and submit form.

#156 빨강과 파랑

Time limit: 1500 ms
Memory limit: 1024 MB
Checker: TOKEN
Solve threshold: 100

Statement

Statement language

A string $S$ of length $N$ is given. Each character of $S$ is either R or B. You can perform the following operation:

Choose an index $i$ : If the $i$ -th character of $S$ is R, change it to B. If it is B, change it to R.

You want to perform given operations so that the set of positions where R appears is either empty or forms a single contiguous interval, and the set of positions where B appears is also either empty or forms a single contiguous interval. Find the minimum number of operations required.

Input

The input is given in the following format.

$N$ $S$

Output

Print the minimum number of operations required.

Constraints

$1 \le N \le 300\,000$ .
$S$ is a string of length $N$ consisting only of the characters R and B.

Subtasks

#	Score	Constraints
1	11	$N \le 20$ .
2	24	$N \le 2\,000$ .
3	27	$N \le 100\,000$ .
4	38	No additional constraints.

Samples

Sample 1

Input

5
RBRBR

Output

Sample 2

Input

6
RRRBBB

Output