P10327 [UESTCPC 2024] Tower of Hanoi Sorting Problem

Natsuzora is playing a Tower of Hanoi with special rules. There are three pegs, $A$, $B$, and $C$. Disks can be stacked on each peg. Disks may be moved between pegs, but the following rules must be followed: - Only one disk can be moved at a time. - Each move can only take the top disk of one peg and place it onto the top of another peg. - On pegs $B$ and $C$, it is not allowed to place any disk on top of another disk that is smaller than it. - **On peg $A$, it is allowed to place a larger disk on top of a smaller disk.** At the beginning, Natsuzora stacks $n$ disks of distinct sizes in a random order on peg $A$, leaving pegs $B$ and $C$ empty. Under the rules above, Natsuzora wants to know the minimum number of moves needed to move all disks from peg $A$ to peg $B$.

The first line contains an integer $T$ $(1\leq T\leq 10^4)$, representing the number of test cases. For each test case, the first line contains an integer $n$ $(1\leq n\leq 10^5)$, representing the number of disks on peg $A$ in the initial state. The second line of each test case contains $n$ integers $p_1,p_2,\ldots,p_n$ $(1\leq p_i\leq n)$, where $p_i$ is the diameter of the $i$-th disk on peg $A$ **from bottom to top**. The testdata guarantees that $p_1,p_2,\ldots,p_n$ is a permutation of length $n$, meaning each integer from $1$ to $n$ appears exactly once in the sequence. For all test cases, it is guaranteed that $\sum n\leq 2\times 10^5$.

For each test case, output one integer per line, representing the minimum number of moves required.

In the first sample, one feasible move sequence with the minimum number of moves is as follows ($X\rightarrow Y$ means moving the top disk of peg $X$ to the top of peg $Y$): 1. $A\rightarrow C$ 2. $A\rightarrow B$ 3. $A\rightarrow C$ 4. $B\rightarrow C$ 5. $A\rightarrow B$ 6. $C\rightarrow A$ 7. $C\rightarrow A$ 8. $C\rightarrow B$ 9. $A\rightarrow B$ 10. $A\rightarrow B$ 11. $A\rightarrow B$ Translated by ChatGPT 5