{"problem":{"name":"[EC Final 2022] Minimum Suffix","description":{"content":"For a string $s$ of length $n$, we define $p_j = x$ if $s[x\\ldots j]$ is the minimum suffix of $s[1\\ldots j]$, for all $j=1,\\ldots, n$. (A suffix is the minimum suffix of a string if it is lexicograph","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9719"},"statements":[{"statement_type":"Markdown","content":"For a string $s$ of length $n$, we define $p_j = x$ if $s[x\\ldots j]$ is the minimum suffix of $s[1\\ldots j]$, for all $j=1,\\ldots, n$. (A suffix is the minimum suffix of a string if it is lexicographically smaller than any other suffix of that string.)\n\nYou are to recover $s$ from $p_1,\\ldots, p_n$. If there are multiple answers, find the lexicographically smallest one.\n\n## Input\n\nThe first line contains a single integer $T$ ($1\\le T\\le 10^5$) representing the number of test cases.\n\nFor each test case, the first line contains a single integer $n$ ($1\\le n\\le 3\\times 10^6$) representing the length of $s$. The next line contains $n$ integers $p_1,\\ldots, p_n$ ($1\\le p_i\\le i$ for all $1\\le i\\le n$).\n\nIt is guaranteed that the sum of $n$ over all test cases does not exceed $3\\times 10^6$.\n\n## Output\n\nFor each test case, output one line. If there is no solution, output $-1$. Otherwise, output the lexicographically smallest $s$. Characters of $s$ are represented by positive integers. Smaller integers represent smaller characters in the lexicographical order.\n\n[samples]\n\n## Note\n\nAs the input/output can be huge, it is recommended to use fast input/output methods.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9719","tags":["字符串","2022","O2优化","ICPC","Lyndon 分解","EC Final"],"sample_group":[["6\n3\n1 1 1\n3\n1 1 2\n3\n1 1 3\n3\n1 2 1\n3\n1 2 2\n3\n1 2 3","1 2 2\n-1\n1 2 1\n1 1 2\n2 1 2\n1 1 1"]],"created_at":"2026-03-03 11:09:25"}}