{"code":"permutationminimization","name":"Permutation Minimization","description":"Cho một hoán vị $p$ gồm $n$ số (từ $1$ đến $n$).\r\nBạn có một `deque` (hàng đợi hai đầu) ban đầu rỗng.\r\n\r\nBạn sẽ duyệt qua các phần tử của hoán vị $p$ theo đúng thứ tự, từ $p_1$ đến $p_n$. Với mỗi phần tử $p_i$, bạn phải đưa nó vào **đầu** hoặc **cuối** `deque`.\r\n\r\nHãy tìm cách thêm phần tử để `deque` cuối cùng (sau khi đã thêm $n$ phần tử) là dãy có **thứ tự từ điển nhỏ nhất** có thể.\r\n\r\n(Lưu ý: Dãy $x$ nhỏ hơn dãy $y$ theo thứ tự từ điển nếu tại vị trí $i$ đầu tiên mà chúng khác nhau, ta có $x_i < y_i$. VD: $[1,2,3] < [1,2,4]$)\r\n\r\n---\r\n\r\n#### **Ràng buộc**\r\n\r\n* $1 \\le t \\le 1000$ (Số lượng test cases).\r\n* $1 \\le n \\le 2 \\times 10^5$ (Kích thước hoán vị).\r\n* $1 \\le p_i \\le n$ (Các phần tử $p_i$ là duy nhất).\r\n* Tổng của $n$ trên tất cả các test cases không vượt quá $2 \\times 10^5$.\r\n\r\n---\r\n\r\n#### **Input**\r\n\r\n- Dòng đầu tiên chứa số nguyên $t$ — số lượng test cases.\r\n- Mỗi test case được mô tả bởi $2t$ dòng tiếp theo:\r\n    - Dòng đầu tiên của test case chứa số nguyên $n$.\r\n    - Dòng thứ hai chứa $n$ số nguyên $p_1, p_2, \\dots, p_n$ — hoán vị $p$.\r\n\r\n---\r\n\r\n#### **Output**\r\n\r\n- Với mỗi test case, in ra $n$ số nguyên trên một dòng — dãy có thứ tự từ điển nhỏ nhất có thể thu được trong `deque`.\r\n\r\n---\r\n\r\n### **VíDụ**\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n\r\n        ```sample\r\n        5\r\n        4\r\n        3 1 2 4\r\n        3\r\n        3 2 1\r\n        3\r\n        3 1 2\r\n        2\r\n        1 2\r\n        2\r\n        2 1\r\n        ```\r\n\r\n    ???+ success \"Output\"\r\n\r\n        ```sample\r\n        1 3 2 4\r\n        1 2 3\r\n        1 3 2\r\n        1 2\r\n        1 2\r\n        ```\r\n\r\n    ??? warning \"Note\"\r\n        Giải thích cho test case đầu tiên ($p = [3, 1, 2, 4]$):\r\n        Một trong những cách để đạt được dãy nhỏ nhất là:\r\n        1.  Thêm `3` vào cuối `deque`. `deque` = `[3]`.\r\n        2.  Thêm `1` vào đầu `deque`. `deque` = `[1, 3]`.\r\n        3.  Thêm `2` vào cuối `deque`. `deque` = `[1, 3, 2]`.\r\n        4.  Thêm `4` vào cuối `deque`. `deque` = `[1, 3, 2, 4]`.\r\n\r\n        Kết quả `[1, 3, 2, 4]` là dãy có thứ tự từ điển nhỏ nhất có thể.","points":100.0,"partial":true,"time_limit":1.0,"memory_limit":1024000,"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}}