You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在一个魔法森林中，有三根古老而神秘的魔法柱子，分别被称为 A 柱、B 柱和 C 柱。在 A 柱上堆放着 $2n$ 个由魔法石制作的圆盘，这些圆盘共有 $n$ 种不同的尺寸，每种尺寸各有两个圆盘。需要注意的是，同一种尺寸的两个圆盘没有区别（例如，它们的魔法力量完全相同）。下图展示了当 $n=3$ 时的初始情况：

作为魔法师，你的任务是将所有圆盘从 A 柱移动到 C 柱，过程中可以借助 B 柱这个中转柱。移动时需要满足以下规则：

1. 每次只能移动一个圆盘；
2. 无论是在 A 柱、B 柱还是 C 柱上，圆盘的排列都必须始终保持“上小下大”的顺序，即较小的圆盘只能放在较大的圆盘之上。

任务：设 $A_n$ 为将 $2n$ 个圆盘从 A 柱移动到 C 柱所需的最少移动次数。对于给定的 $n$，请输出 $A_n$。

输入格式

一个正整数 $n$，表示初始在 A 柱上有 $2n$ 个圆盘。

输出格式

一个正整数，表示完成任务所需的最少移动次数 $A_n$。

样例 #1

样例输入 #1

1

样例输出 #1

2

样例 #2

样例输入 #2

2

样例输出 #2

6

提示

限制

• 对于 $50\%$ 的数据，$1 \leq n \leq 25$；
• 对于 $100\%$ 的数据，$1 \leq n \leq 200$。