{"code":"xepbong","name":"Xếp Bóng","description":"Cho $N \\times 2$ quả bóng gồm $N$ quả bóng màu vàng và $N$ quả bóng màu xanh dương được đặt trong một hàng dọc được kí hiệu là $color_i$ và $a_i$. Trong đó $color_i$ tượng trưng cho màu của quả bóng, $color_i$ là ```yellow``` nếu quả bóng đó là màu vàng và $color_i$ là ```blue``` nếu quả bóng đó là màu xanh dương và $a_i$ là số thứ tự của quả bóng $(1\\le a_i\\le N)$.\r\n\r\nLúc đầu các quả bóng được sắp xếp ngẫu nhiên, [user:shiba] muốn sắp xếp các quả bóng bằng cách hoán đổi vị trí của hai quả bóng liền kề nhau cho đến khi $N$ quả bóng màu vàng được sắp theo tăng dần từ trên xuống dưới theo số thứ tự và $N$ quả bóng màu xanh dương được sắp theo tăng dần từ trên xuống dưới theo số thứ tự\r\n\r\nBiết rằng [user:shiba] có thể thay đổi vị trí nhiều lần hoặc có thể không cần đổi, và mỗi lần chỉ được hoán đổi vị trí của hai quả bóng liền kề nhau. [user:shiba] chỉ quan tâm $N$ quả bóng màu vàng được sắp theo tăng dần hay chưa (tương tự với quả bóng màu xanh dương) mà không cần quan tâm màu gì đứng trước màu gì.\r\n\r\n**Yêu cầu:** Bạn hãy tìm số lần thực hiện thao tác ít nhất có thể để các quả bóng được sắp xếp theo đúng mong muốn của [user:shiba].\r\n\r\n#### Input\r\n - Dòng đầu tiên chứa số nguyên dương $N$  $(1 \\le N \\le 2000)$.\r\n - \t$N \\times 2$ Dòng tiếp theo mỗi dòng chứa hai giá trị $color_i$ và $a_i$\r\n   $(color_i =$ ```yellow``` hoặc  $color_i =$ ```blue```, $1 \\le a_i\r\n   \\le N)$.\r\n - \tInput luôn đảm bảo rằng số thứ tự của mỗi màu không bị trùng lặp.\r\n\r\n#### Output\r\n - In ra số lần thực hiện thao tác ít nhất có thể để các quả bóng được sắp xếp theo đúng các điều kiện trên.\r\n\r\n#### Scoring\r\n - Subtask $1$ ($20\\%$ số điểm): Có $N \\le 10$.\r\n - Subtask $2$ ($80\\%$ số điểm): Không có ràng buộc gì thêm.\r\n\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3\r\n        yellow 2\r\n        blue 3\r\n        yellow 1\r\n        blue 1\r\n        blue 2\r\n        yellow 3\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        4\r\n        ```\r\n    ??? warning \"Note\"\r\n        [user:shiba] sẽ sắp xếp theo trình tự như sau:\r\n         1. Đổi vị trí blue 3 và yellow 1. Lúc này bóng đang được sắp xếp như sau: \r\n            - yellow 2\r\n            - yellow 1\r\n            - blue 3\r\n            - blue 1\r\n            - blue 2\r\n            - yellow 3\r\n\r\n        2. Đổi vị trí blue 3 và blue 1. Lúc này bóng đang được sắp xếp như sau:\r\n\r\n            - yellow 2\r\n            - yellow 1\r\n            - blue 1\r\n            - blue 3\r\n            - blue 2\r\n            - yellow 3\r\n    \r\n        3. Đổi vị trí blue 2 và blue 3. Lúc này bóng đang được sắp xếp như sau:\r\n\r\n            - yellow 2\r\n            - yellow 1\r\n            - blue 1\r\n            - blue 2\r\n            - blue 3\r\n            - yellow 3\r\n    \r\n        4. Đổi vị trí yellow 2 và yellow 1. Lúc này bóng đang được sắp xếp như sau:\r\n\r\n            - yellow 1\r\n            - yellow 2\r\n            - blue 1\r\n            - blue 2\r\n            - blue 3\r\n            - yellow 3\r\n\r\n        Ta thấy rằng trình tự của bóng đã đúng như ý muốn của [user:shiba]. Vậy số lần thao tác [user:shiba] cần thực hiện là $4$.\r\n        Bạn có thể sắp xếp bằng bất kì cách nào, miễn nó thỏa mãn rằng số lần sắp xếp là ít nhất.\r\n        \r\n!!! question \"Test 2\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        5\r\n        blue 3\r\n        blue 2\r\n        blue 5\r\n        yellow 4\r\n        blue 4\r\n        yellow 1\r\n        yellow 5\r\n        blue 1\r\n        yellow 2\r\n        yellow 3\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        15\r\n        ```","points":2000.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}