Una expresión válida se define de forma recursiva:

• x es una expresión válida;
• si $A$ y $B$ son expresiones válidas, entonces $(AB)$ también es una expresión válida.

Por ejemplo, ((xx)(x(xx))) es una expresión válida con cinco apariciones de x. Cada expresión válida corresponde a un árbol binario: cada x es una hoja, y cada par de paréntesis es un nodo interno cuyos hijos son las dos subexpresiones que encierra.

En una operación, puedes reemplazar una subexpresión de la forma $((AB)C)$ por $(A(BC))$, donde $A$, $B$ y $C$ son expresiones válidas arbitrarias. En la representación mediante árboles, esto hace girar una sola arista.

Decimos que una expresión $u$ puede obtenerse a partir de una expresión $v$ si $u$ puede producirse a partir de $v$ aplicando cero o más operaciones. En particular, toda expresión puede obtenerse a partir de sí misma.

Se te da un entero $\ell$. El número de expresiones válidas con exactamente $\ell$ apariciones de x es el número de Catalan

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

y todas ellas se enumeran en orden lexicográfico como $S_1,S_2,\ldots,S_n$, usando el orden de caracteres $\texttt{(}<\texttt{x}<\texttt{)}$. Aquí, $\binom{a}{b}=\frac{a!}{b!(a-b)!}$ es el coeficiente binomial.

También se te da una permutación $p_1,p_2,\ldots,p_n$ de los enteros de $1$ a $n$; el valor $p_i$ representa la expresión $S_{p_i}$. Cuenta los pares $(i,j)$ con $1\le i<j\le n$ tales que $S_{p_i}$ puede obtenerse a partir de $S_{p_j}$.

Entrada

La primera línea contiene un entero $\ell$ ($1\le\ell\le14$).

La segunda línea contiene $n=C_{\ell-1}$ enteros $p_1,p_2,\ldots,p_n$: una permutación de $1,2,\ldots,n$.

Salida

Imprime un entero: el número de pares $(i,j)$ tales que $1\le i<j\le n$ y $S_{p_i}$ puede obtenerse a partir de $S_{p_j}$.

Ejemplos

Entrada 1

4
3 1 5 2 4

Salida 1

3

Nota

Para $\ell=4$ hay $n=C_3=5$ expresiones válidas, en orden lexicográfico: $S_1=$ (((xx)x)x), $S_2=$ ((x(xx))x), $S_3=$ ((xx)(xx)), $S_4=$ (x((xx)x)), $S_5=$ (x(x(xx))).

Una sola operación transforma $S_1$ en $S_2$ o en $S_3$, transforma $S_2$ en $S_4$, y transforma tanto $S_3$ como $S_4$ en $S_5$; no se puede aplicar ninguna operación a $S_5$.

Los tres pares que se cuentan son $(i,j)=(1,2)$, puesto que $S_3$ puede obtenerse a partir de $S_1$; $(3,4)$, puesto que $S_5$ puede obtenerse a partir de $S_2$; y $(3,5)$, puesto que $S_5$ puede obtenerse a partir de $S_4$.