JOI là người giỏi làm vườn tại nhà. Cậu trồng cỏ Joy trong khu vườn của mình. Có \(N\) chậu cây được xếp thành một hàng theo hướng đông-tây, đánh số từ \(1\) đến \(N\) tính từ đầu phía tây. Có \(N\) cây cỏ Joy, mỗi chậu trồng một cây.

Vào mùa xuân, trái với dự đoán, JOI nhận thấy cỏ Joy mọc lá có nhiều màu khác nhau. Cậu còn thấy cây không phát triển tốt như mong đợi. Tra cứu sách, cậu biết được rằng:

• Có ba loại cỏ Joy, lần lượt có lá màu đỏ, xanh lá và vàng.
• Nếu các cây cỏ Joy có cùng màu lá được đặt gần nhau, sự phát triển của chúng sẽ bị cản trở.

Vì vậy, JOI quyết định sắp xếp lại sao cho không có hai cây cùng màu lá đứng cạnh nhau. Do các chậu rất nặng, trong mỗi thao tác cậu chỉ có thể hoán đổi hai cây ở hai chậu kề nhau. Cụ thể, cậu chọn một chỉ số \(i\) với \(1 \le i \le N-1\) rồi hoán đổi cây ở chậu \(i\) và chậu \(i+1\).

Hãy tính số thao tác ít nhất cần thực hiện để không có hai cây cùng màu lá đứng cạnh nhau.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo định dạng:

N
S

\(S\) là chuỗi độ dài \(N\). Ký tự thứ \(i\) là R, G hoặc Y nếu cây ở chậu \(i\) có lá lần lượt màu đỏ, xanh lá hoặc vàng.

Dữ liệu ra

In ra một dòng chứa số thao tác ít nhất cần thực hiện. Nếu không thể sắp xếp để không có hai cây cùng màu lá đứng cạnh nhau, in ra \(-1\).

Ràng buộc

• \(N\) là số nguyên và \(1 \le N \le 400\).
• \(S\) có độ dài \(N\).
• Mỗi ký tự của \(S\) là R, G hoặc Y.

Phân nhóm

1. \(5\) điểm: \(1 \le N \le 15\); \(S\) có độ dài \(N\) và chỉ gồm R, G, Y.
2. \(55\) điểm: \(1 \le N \le 60\); \(S\) có độ dài \(N\) và chỉ gồm R, G, Y.
3. \(15\) điểm: \(1 \le N \le 400\); \(S\) có độ dài \(N\) và chỉ gồm R, G.
4. \(25\) điểm: \(1 \le N \le 400\); \(S\) có độ dài \(N\) và chỉ gồm R, G, Y.

Ví dụ

5
RRGYY

2

6
RRRRRG

-1

20
YYGYYYGGGGRGYYGRGRYG

8

Nguồn

Bản dịch tiếng Việt từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản, vòng chung kết JOI 2018/2019, bài 3. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.