{"problem":{"name":"「Cfz Round 3」Sum of Permutation","description":{"content":"**请注意本题特殊的时间限制。** 给定一个 $1\\sim n$ 的排列 $p$。 你需要构造一个长度为 $n$ 的序列 $a$，满足： - 序列 $a$ 中的每个元素均为不大于 $n$ 的正整数； - 不存在有序整数二元组 $(l,r)$，满足 $1 \\le l \\le r \\le n$ 且 $\\sum\\limits_{i=l}^r a_i=\\sum\\limits_{i=l}^r p_i$","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10033"},"statements":[{"statement_type":"Markdown","content":"**请注意本题特殊的时间限制。**\n\n给定一个 $1\\sim n$ 的排列 $p$。\n\n你需要构造一个长度为 $n$ 的序列 $a$，满足：\n\n- 序列 $a$ 中的每个元素均为不大于 $n$ 的正整数；\n- 不存在有序整数二元组 $(l,r)$，满足 $1 \\le l \\le r \\le n$ 且 $\\sum\\limits_{i=l}^r a_i=\\sum\\limits_{i=l}^r p_i$；\n\n或报告无解。\n\n其中，$1\\sim n$ 的排列指满足所有不大于 $n$ 的正整数恰好出现一次的序列。\n\n## Input\n\n**本题有多组测试数据。**\n\n第一行输入一个整数 $T$，表示测试数据组数。\n\n接下来依次输入每组测试数据。对于每组测试数据：\n\n- 第一行输入一个整数 $n$。\n- 第二行输入 $n$ 个整数，表示给定的排列 $p$。\n\n## Output\n\n对于每组数据，输出一行：\n\n- 若存在满足条件的序列 $a$，则输出用空格分隔的 $n$ 个整数，表示你构造的序列 $a$；\n- 若不存在满足条件的序列 $a$，则输出 $-1$。\n\n**所有满足要求的输出均可通过。**\n\n[samples]\n\n## Note\n\n#### 「样例解释 #1」\n\n对于第 $1$ 组数据，$\\{1,3,3\\}$ 和 $\\{1,1,3\\}$ 均为满足条件的序列 $a$。\n\n对于第 $2$ 组数据，可以证明不存在满足条件的序列 $a$。\n\n对于第 $3$ 组数据，除 $\\{5,3,2,1,1 \\}$ 外，$\\{3,4,5,3,2 \\}$、$\\{1,4,5,3,4 \\}$、$\\{5,3,3,4,5\\}$ 等均为满足条件的序列 $a$。\n\n#### 「数据范围」\n\n设 $\\sum n$ 表示单个测试点中 $n$ 的和。\n\n对于所有数据，$1 \\le T \\le 5000$，$2 \\le n \\le 10^6$，$\\sum n \\le 10^6$，保证 $p$ 是 $1\\sim n$ 的排列。\n\n**只有你通过本题的所有测试点，你才能获得本题的分数。**\n\n**本题输入输出量较大，请使用较快的输入输出方式。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10033","tags":["数学","洛谷原创","Special Judge","O2优化","构造","洛谷月赛","Ad-hoc"],"sample_group":[["4\n3\n3 2 1\n2\n1 2\n5\n4 2 1 5 3\n7\n5 7 3 1 2 4 6","1 3 3\n-1\n5 3 2 1 1\n2 3 5 4 6 3 1"]],"created_at":"2026-03-03 11:09:25"}}