{"code":"2022usopenplatinum3","name":"USACO 2022 US Open Contest, Platinum, Up Down Subsequence","description":"Nông dân John có $N$ con bò $(2 \\le N \\le 3 \\times 10^5)$ được đánh số từ $1$ đến $N$ như thường lệ. Những chú bò này đã xếp hàng thành một hoán vị $p_1, p_2, \\dots, p_N$. Bạn được cho một chuỗi dài $N - 1$ chỉ bao gồm kí tự `U` và `D`. Hãy tìm ra số $K \\le N - 1$ lớn nhất sao cho tồn tại đãy con $a_0, a_1, \\dots, a_K$ của $p$ thoả mãn với mọi $1 \\le j \\le K, a_{j - 1} < a{j}$ nếu kí tự thứ $j$ trong chuỗi là `U` và $a_{j - 1} > a{j}$ nếu kí tự thứ $j$ trong chuỗi là `D`.\r\n\r\n#### Input\r\n- Dòng đầu tiên là số $N$.\r\n- Dòng tiếp theo là các số $p_1, p_2, \\dots, p_N$.\r\n- Dòng cuối cùng là chuỗi được cho.\r\n\r\n#### Output\r\n- Số $K$ thoả mãn.\r\n\r\n#### Scoring\r\n- Subtask $1$: $N \\le 500$.\r\n- Subtask $2$: $N \\le 5000$.\r\n- Subtask $3$: Phần đầu của chuỗi chỉ toàn kí tự `U` sau đó chỉ toàn kí tự `D`.\r\n- Subtask $4$: Không có thêm ràng buộc.\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```\r\n        5\r\n        1 5 3 4 2\r\n        UDUD\r\n        ```\r\n    ???+ \"Output\"\r\n        ```\r\n        4\r\n        ```\r\n    ??? warning \"Note\"\r\n        Có thể chọn $[a_0, a_1, a_2, a_3, a_4] = [p_1, p_2, p_3, p_4, p_5]$.\r\n        \r\n\r\n!!! question \"Test 2\"\r\n    ???+ \"Input\"\r\n        ```\r\n        5\r\n        1 5 3 4 2\r\n        UUDD\r\n        ```\r\n    ???+ \"Output\"\r\n        ```\r\n        3\r\n        ```\r\n    ??? warning \"Note\"\r\n        Có thể chọn $[a_0, a_1, a_2, a_3] = [p_1, p_3, p_4, p_5]$.","points":1000.0,"partial":true,"time_limit":2.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}}