{"problem":{"name":"橙垒球","description":{"content":"垒球很喜欢一个叫迷你某·萨菲克斯的题，并且很崇拜这题的出题人，所以出了个差不多的题。 给定一个长度为 $n$ 的序列 $a_1,\\ldots,a_n$，请构造一个**字典序最大**的长度为 $n$ 的字符串 $w$，使得： - $w$ 的每个字符是 $1$ 到 $n$ 的整数，字符的大小顺序为 $1$ 最小 $n$ 最大； - $w$ 的长度为 $i$ 的前缀的**字典序最大的后缀**长度恰","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9395"},"statements":[{"statement_type":"Markdown","content":"垒球很喜欢一个叫迷你某·萨菲克斯的题，并且很崇拜这题的出题人，所以出了个差不多的题。\n\n给定一个长度为 $n$ 的序列 $a_1,\\ldots,a_n$，请构造一个**字典序最大**的长度为 $n$ 的字符串 $w$，使得：\n\n- $w$ 的每个字符是 $1$ 到 $n$ 的整数，字符的大小顺序为 $1$ 最小 $n$ 最大；\n\n- $w$ 的长度为 $i$ 的前缀的**字典序最大的后缀**长度恰为 $a_i$。\n\n请输出这样的 $w$，或报告无解。\n\n本题单个测试点包含多组数据。\n\n## Input\n\n第一行：一个整数 $T$，表示数据组数。\n\n接下来依次输入 $T$ 组数据，对于每组数据：\n\n第一行：一个整数 $n$。\n\n第二行：$n$ 个整数 $a_1,\\ldots,a_n$。\n\n## Output\n\n对于每组数据：\n\n若无解，只输出一行一个 $-1$。\n\n若有解，则输出一行 $n$ 个整数，表示你给出的 $w$。\n\n[samples]\n\n## Note\n\n**【样例解释】**\n\n字符串 $1,2,3$ 的每个前缀的最大后缀长度恰好为 $1,1,1$，且是满足这个条件的字典序最大的字符串。\n\n字符串 $2,3,3$ 的每个前缀的最大后缀长度恰好为 $1,1,2$，且是满足这个条件的字典序最大的字符串。\n\n不存在一个字符串，每个前缀的最大后缀长度恰好为 $1,1,3$。\n\n字符串 $2,2,3$ 的每个前缀的最大后缀长度恰好为 $1,2,1$，且是满足这个条件的字典序最大的字符串。\n\n不存在一个字符串，每个前缀的最大后缀长度恰好为 $1,2,2$。\n\n字符串 $3,3,3$ 的每个前缀的最大后缀长度恰好为 $1,2,3$，且是满足这个条件的字典序最大的字符串。\n\n---\n\n**【评分方式】**\n\n每个测试点的分数等于其中所有测试数据分数的最小值。一个测试数据的分数由以下方式确定：\n\n如果你的输出格式错误（即不符合输出格式的要求），则不能得分。\n\n否则，如果你正确判定了是否有解（即在无解的数据输出 $-1$，有解的数据输出了 $n$ 个 $[1,n]$ 中的数），则可以获得 $20\\%$ 的分数。\n\n在此基础上，如果该测试点无解，或者有解且你输出的是一组合法解（未必是字典序最大的），则可以再获得 $30\\%$ 的分数。\n\n在此基础上，如果该测试点无解，或者有解且你输出的是字典序最大的解，则可以再获得 $50\\%$ 的分数。\n\n---\n\n**【数据范围】**\n\n对于全部数据：$1\\leq T\\leq 10000$，$1 \\le n \\le 4 \\times 10 ^ 6$，$\\sum n\\leq 4\\times 10^6$，$1\\leq a_i\\leq i$。\n\n|     子任务编号     |  $\\sum n\\leq$  | 特殊性质 | 分值 |\n| :----------------: | :------------: | :------: | :--: |\n| $\\text{Subtask 1}$ | $4\\times 10^6$ | 保证无解 | $1$  |\n| $\\text{Subtask 2}$ | $4\\times 10^5$ | 保证有解 | $29$ |\n| $\\text{Subtask 3}$ | $4\\times 10^6$ |    无    | $70$ |\n\n---\n\n**【提示】**\n\n请使用较快速的输入输出方式。\n\n---\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/5ofelxu1.png)","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9395","tags":["洛谷原创","Special Judge","O2优化","洛谷月赛"],"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\n","1 2 3\n2 3 3\n-1\n2 2 3\n-1\n3 3 3\n"]],"created_at":"2026-03-03 11:09:25"}}