Những viên đá trên bàn (Stones on the Table)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ viên đá nằm thành một hàng từ trái sang phải. Mỗi viên mang màu R, G hoặc B. Được phép xóa bớt viên và nối các viên còn lại theo đúng thứ tự ban đầu. Hãy tính ít nhất bao nhiêu viên cần xóa để hai viên còn lại bất kỳ đứng kề nhau đều khác màu.

Input

Dòng đầu chứa $n$, dòng tiếp theo chứa đúng $n$ ký tự thuộc R, G, B liên tiếp.

Output

Một số nguyên là số viên ít nhất phải xóa.

Subtask

• Subtask 1 (20%): $1\le n\le5$.
• Subtask 2 (30%): $1\le n\le20$.
• Subtask 3 (50%): $1\le n\le50$.

Ví dụ

Ví dụ 1

Input

3
RRG

Output

1

Giải thích

Hai viên R đầu cùng màu tạo thành một đoạn R dài 2, chỉ cần bỏ một trong hai. Viên G đã khác màu, nên in 1.

Ví dụ 2

Input

5
RRRRR

Output

4

Giải thích

Có năm viên cùng màu, chỉ giữ tối đa một viên nên xóa bốn viên.