올바른 식은 다음과 같이 재귀적으로 정의됩니다.

• $x$는 올바른 식입니다.
• $A$와 $B$가 올바른 식이면 $(AB)$도 올바른 식입니다.

예를 들어, $((xx)(x(xx)))$는 $x$가 다섯 번 등장하는 올바른 식입니다. 모든 올바른 식은 이진 트리에 대응합니다. 각 $x$는 리프이고, 각 괄호 쌍은 그 안에 있는 두 부분식을 자식으로 가지는 내부 정점입니다.

한 번의 연산으로 $((AB)C)$ 형태의 부분식을 $(A(BC))$로 바꿀 수 있습니다. 여기서 $A$, $B$, $C$는 임의의 올바른 식입니다. 트리 표현에서 이는 하나의 간선을 회전하는 것에 해당합니다.

식 $v$에 연산을 0번 이상 적용하여 식 $u$를 만들 수 있다면, 식 $u$를 식 $v$로부터 얻을 수 있다고 합니다. 특히 모든 식은 자기 자신으로부터 얻을 수 있습니다.

정수 $\ell$이 주어집니다. $x$가 정확히 $\ell$번 등장하는 올바른 식의 수는 카탈란 수

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

이며, 이 식들을 문자 순서 $\texttt{(}<\texttt{x}<\texttt{)}$를 사용하여 사전순으로 $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)$의 수를 구하세요.

입력

첫 번째 줄에 정수 $\ell$ ($1\le\ell\le14$)이 주어집니다.

두 번째 줄에 $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

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)))$입니다.

한 번의 연산으로 $S_1$을 $S_2$ 또는 $S_3$으로, $S_2$를 $S_4$로, $S_3$과 $S_4$ 각각을 $S_5$로 바꿀 수 있습니다. $S_5$에는 적용할 수 있는 연산이 없습니다.

세어야 하는 세 쌍은 다음과 같습니다. $S_3$을 $S_1$로부터 얻을 수 있으므로 $(i,j)=(1,2)$, $S_5$를 $S_2$로부터 얻을 수 있으므로 $(3,4)$, 그리고 $S_5$를 $S_4$로부터 얻을 수 있으므로 $(3,5)$입니다.