[UESTCPC 2024] 汉诺塔排序问题

Natsuzora 在玩一个特殊规则的汉诺塔。 汉诺塔有 $A$、$B$、$C$ 共三根柱子，每根柱子上可以堆叠放置圆盘。圆盘可以在不同柱子之间移动，但必须遵守以下规则： - 一次只有一个圆盘被移动； - 每次移动只能将一个柱子最顶端的圆盘移动到另一个柱子的最顶端； - 在柱子 $B$ 和 $C$ 上，不允许任何圆盘放置在另外一个比它本身小的圆盘上； - **在柱子 $A$ 上，允许将较大的圆盘放置在较小的圆盘上。** 最开始时，Natsuzora 将 $n$ 个大小互不相同的圆盘乱序地摞在 $A$ 柱子上并将柱子 $B$ 和 $C$ 留空。在满足上述条件的情况下，Natsuzora 想要知道，若要将 $A$ 柱上的圆盘全部移动到 $B$ 柱上，他至少需要进行多少次移动。

第一行包含一个整数 $T$ $(1\leq T\leq 10^4)$，表示数据组数。 每组数据的第一行包含一个整数 $n$ $(1\leq n\leq 10^5)$，表示初始状态下柱子 $A$ 上的圆盘数量。 每组数据的第二行包含 $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$ 中的每个整数都在序列中出现恰好一次。 对于所有数据，保证 $\sum n\leq 2\times 10^5$。

对于每组数据，输出一行一个整数，表示需要的最少移动次数。

3
5
1 5 3 2 4
5
1 2 3 4 5
6
5 3 6 1 4 2

11
5
19

在第一个样例中，一种可行的次数最少的移动方案如下（$X\rightarrow Y$ 表示将柱子 $X$ 最顶上的圆盘移动到柱子 $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$