有効な式を再帰的に次のように定義します。

• x は有効な式です。
• $A$ と $B$ が有効な式であるとき、$(AB)$ も有効な式です。

例えば、((xx)(x(xx))) は x が 5 回出現する有効な式です。すべての有効な式は二分木に対応します。各 x は葉であり、各括弧の組は、その括弧で囲まれた 2 つの部分式を子として持つ内部頂点です。

1 回の操作では、$((AB)C)$ という形の部分式を $(A(BC))$ に置き換えることができます。ここで、$A$、$B$、$C$ は任意の有効な式です。木による表現では、この操作は 1 本の辺を回転させることに対応します。

式 $v$ に操作を 0 回以上適用して式 $u$ を作ることができるとき、$u$ は $v$ から得られるといいます。特に、どの式も自分自身から得られます。

整数 $\ell$ が与えられます。x がちょうど $\ell$ 回出現する有効な式の個数は、カタラン数

$$n=C_{\ell-1}=\frac{1}{\ell}\binom{2\ell-2}{\ell-1}$$

です。これらの式をすべて、文字の順序を '(' $<$ 'x' $<$ ')' とした辞書順に $S_1,S_2,\ldots,S_n$ と列挙します。ここで、$\binom{a}{b}=\frac{a!}{b!(a-b)!}$ は二項係数です。

さらに、$1$ から $n$ までの整数の順列 $p_1,p_2,\ldots,p_n$ が与えられます。値 $p_i$ は式 $S_{p_i}$ を表します。$1\le i<j\le n$ であり、$S_{p_i}$ が $S_{p_j}$ から得られるような組 $(i,j)$ の個数を求めてください。

入力

1 行目には整数 $\ell$ ($1\le\ell\le14$) が 1 つ与えられます。

2 行目には $n=C_{\ell-1}$ 個の整数 $p_1,p_2,\ldots,p_n$ が与えられます。これらは $1,2,\ldots,n$ の順列です。

出力

$1\le i<j\le n$ であり、$S_{p_i}$ が $S_{p_j}$ から得られるような組 $(i,j)$ の個数を、1 つの整数として出力してください。

入出力例

入力 1

4
3 1 5 2 4

出力 1

3

注記

$\ell=4$ のとき、有効な式は $n=C_3=5$ 個あり、辞書順に、$S_1=$ (((xx)x)x)、$S_2=$ ((x(xx))x)、$S_3=$ ((xx)(xx))、$S_4=$ (x((xx)x))、$S_5=$ (x(x(xx))) です。

1 回の操作で $S_1$ は $S_2$ または $S_3$ に、$S_2$ は $S_4$ に、$S_3$ と $S_4$ はそれぞれ $S_5$ に変わります。$S_5$ に適用できる操作はありません。

数えられる 3 つの組は、$S_3$ が $S_1$ から得られることによる $(i,j)=(1,2)$、$S_5$ が $S_2$ から得られることによる $(3,4)$、そして $S_5$ が $S_4$ から得られることによる $(3,5)$ です。