#1372. SWAPBALL - Tráo bi

Bộ nhớ: 256 MiB Thời gian: 500 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

NGUỒN: Bài tập thầy Hiếu ôn Hải Phòng T11/2020

Cho 𝑛 viên bi, mỗi viên một trong 3 màu 𝑥𝑎𝑛ℎ, đỏ, 𝑣à𝑛𝑔 xếp thành hàng. Bằng các phép trảo đổi 2 bi cạnh nhau, hãy xác định số bước đổi chỗ ít nhất để tất cả các viên bi cùng màu nằm cạnh nhau theo thứ tự 𝑥𝑎𝑛ℎ, đỏ, 𝑣à𝑛𝑔.

Dữ liệu vào:

  • Dòng đầu tiên chứa số nguyên dương 𝑛\ (𝑛 ≤ 10^5) ;
  • Dòng thứ hai chứa 𝑛 số nguyên 1 − 𝑥𝑎𝑛ℎ, 2 − đỏ, 3 − 𝑣à𝑛𝑔.

Dữ liệu ra:

  • Ghi ra một số nguyên xác định số bước đổi chỗ ít nhất để các viên bi được xếp theo thứ tự 𝑥𝑎𝑛ℎ, đỏ, 𝑣à𝑛𝑔.

Ví dụ:

Dữ liệu vào:
6
1 3 2 1 3 2
Dữ liệu ra:
5