{"problem":{"name":"[PA 2022] Chodzenie po linie","description":{"content":"**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 5 [Chodzenie po linie](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/lin/)** Byteasar 是世界著名的马戏团演员，他擅长走钢丝，并在钢丝之间穿行。在他著名的表演中，马戏团帐篷的天花板","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":6000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9265"},"statements":[{"statement_type":"Markdown","content":"**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 5 [Chodzenie po linie](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/lin/)**\n\nByteasar 是世界著名的马戏团演员，他擅长走钢丝，并在钢丝之间穿行。在他著名的表演中，马戏团帐篷的天花板下拉了 $n$ 条钢丝。如果我们俯瞰帐篷，并将其放置在坐标系中，第 $i\\ (i=1,2,\\ldots,n)$ 条钢丝连接点 $(i,0)$ 和点 $(p_i,1)$，其中序列 $p_1,p_2,\\ldots,p_n$ 是 $1$ 到 $n$ 整数的一个排列。\n\nByteasar 站在其中一条钢丝上开始表演，并让观众给他一些钢丝的编号。他的目标是站在观众所说的那条钢丝上面。Byteasar 非常善于沿钢丝移动，但从一条钢丝移动到另一条钢丝是相当复杂的。因为他非常勇敢，但并不愚蠢，只有两条钢丝相交时，他才能从一条钢丝移到另一条钢丝上。所有的钢丝都悬挂在相似的高度，所以这样的移动总能成功，但这是相当累人的。出于这个原因，Byteasar 将选择一条不同钢丝之间交点个数最少的路线。唯一的例外是当以这种方式不可能到达目标钢丝的情况——在这种情况下，Byteasar 将礼貌地感谢观众并回到后台，从而不进行任何穿越。\n\n然而，Byteasar 不确定他应该从哪根钢丝开始他的表演。对于这些钢丝的每一根，他都想知道对于观众所有可能的选择，他最少经过交点个数的和。帮他写一个程序来计算这些值。\n\n## Input\n\n输入第一行一个整数 $n$，表示钢丝数量。\n\n第二行 $n$ 个整数 $p_1,p_2,\\ldots,p_n$，，意义如题目描述。\n\n## Output\n\n输出一行 $n$ 个整数，第 $i$ 个整数表示如果 Byteasar 从第 $i$ 根钢丝出发，对于观众所有可能的选择，他最少经过交点个数的和。\n\n[samples]\n\n## Note\n\n对于 $100\\%$ 的数据，满足：\n\n$1\\le n\\le 2 \\times 10 ^ 5, 1\\le p_i\\le n$，\n\n保证对于任意 $i,j\\ (i\\neq j)$，满足 $p_i\\neq p_j$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9265","tags":["2022","PA（波兰）"],"sample_group":[["7\n2 1 4 7 3 6 5\n","1 1 9 5 6 7 7\n"]],"created_at":"2026-03-03 11:09:25"}}