题目描述

给定 $\red{A,B,C}$ 三根足够长的细柱，在$\red{A}$柱上放有$\red{2n}$个中间有空的圆盘，共有 $\red{n}$ 个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的(下图为$\red{n=3}$的情形）。现要将这些圆盘移到$\red{C}$柱上，在移动过程中可放在$\red{B}$柱上暂存。要求:

$\red{(1)}$每次只能移动一个圆盘；

$\red{(2)A、B、C}$ 三根细柱上的圆盘都要保持上小下大的顺序；

任务:设 $\red{A_n}$ 为 $\red{2n}$ 个圆盘完成上述任务所需的最少移动次数，对于输入的 $\red{n}$，输出 $\red{A_n}$。

输入格式

一个正整数$\red{n}$，表示在$\red{A}$柱上放有$\red{2n}$个圆盘。

输出格式

仅一行，包含一个正整数，为完成上述任务所需的最少移动次数$\red{A_n}$。

样例

输入样例1

1

输出样例1

2

输入样例2

2

输出样例2

6

提示

对于$\red{50 \%}$的数据， $\red{1 \leq n \leq 25}$

对于$\red{100 \%}$ 数据， $\red{1 \leq n \leq 200}$

设法建立$\red{A_n}$与$\red{A_n−1}$的递推关系式。