{"problem":{"name":"[UESTCPC 2024] 汉诺塔排序问题","description":{"content":"Natsuzora 在玩一个特殊规则的汉诺塔。 汉诺塔有 $A$、$B$、$C$ 共三根柱子，每根柱子上可以堆叠放置圆盘。圆盘可以在不同柱子之间移动，但必须遵守以下规则： - 一次只有一个圆盘被移动； - 每次移动只能将一个柱子最顶端的圆盘移动到另一个柱子的最顶端； - 在柱子 $B$ 和 $C$ 上，不允许任何圆盘放置在另外一个比它本身小的圆盘上； - **在柱子 $A$ 上，允许将较大的圆","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10327"},"statements":[{"statement_type":"Markdown","content":"Natsuzora 在玩一个特殊规则的汉诺塔。\n\n汉诺塔有 $A$、$B$、$C$ 共三根柱子，每根柱子上可以堆叠放置圆盘。圆盘可以在不同柱子之间移动，但必须遵守以下规则：\n\n- 一次只有一个圆盘被移动；\n- 每次移动只能将一个柱子最顶端的圆盘移动到另一个柱子的最顶端；\n- 在柱子 $B$ 和 $C$ 上，不允许任何圆盘放置在另外一个比它本身小的圆盘上；\n- **在柱子 $A$ 上，允许将较大的圆盘放置在较小的圆盘上。**\n\n最开始时，Natsuzora 将 $n$ 个大小互不相同的圆盘乱序地摞在 $A$ 柱子上并将柱子 $B$ 和 $C$ 留空。在满足上述条件的情况下，Natsuzora 想要知道，若要将 $A$ 柱上的圆盘全部移动到 $B$ 柱上，他至少需要进行多少次移动。\n\n## Input\n\n第一行包含一个整数 $T$ $(1\\leq T\\leq 10^4)$，表示数据组数。\n\n每组数据的第一行包含一个整数 $n$ $(1\\leq n\\leq 10^5)$，表示初始状态下柱子 $A$ 上的圆盘数量。\n\n每组数据的第二行包含 $n$ 个整数 $p_1,p_2,\\ldots,p_n$ $(1\\leq p_i\\leq n)$，其中 $p_i$ 表示柱子 $A$ **从下往上**第 $i$ 个圆盘的直径。数据保证 $p_1,p_2,\\ldots,p_n$ 是一个长度为 $n$ 的排列，即 $1$ 到 $n$ 中的每个整数都在序列中出现恰好一次。\n\n对于所有数据，保证 $\\sum n\\leq 2\\times 10^5$。\n\n## Output\n\n对于每组数据，输出一行一个整数，表示需要的最少移动次数。\n\n[samples]\n\n## Note\n\n在第一个样例中，一种可行的次数最少的移动方案如下（$X\\rightarrow Y$ 表示将柱子 $X$ 最顶上的圆盘移动到柱子 $Y$ 的顶部）：\n\n  1. $A\\rightarrow C$\n  2. $A\\rightarrow B$\n  3. $A\\rightarrow C$\n  4. $B\\rightarrow C$\n  5. $A\\rightarrow B$\n  6. $C\\rightarrow A$\n  7. $C\\rightarrow A$\n  8. $C\\rightarrow B$\n  9. $A\\rightarrow B$\n  10. $A\\rightarrow B$\n  11. $A\\rightarrow B$","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10327","tags":["2024","O2优化","高校校赛"],"sample_group":[["3\n5\n1 5 3 2 4\n5\n1 2 3 4 5\n6\n5 3 6 1 4 2","11\n5\n19"]],"created_at":"2026-03-03 11:09:25"}}