#P18111. Binary Rotations

Binary Rotations

Binary Rotations

合法表达式按以下规则定义:x 是合法表达式;若 A,BA,B 合法,(AB) 也合法。因此每个表达式对应一棵满二叉树,x 对应叶子,一对括号对应一个内部结点。

一次操作可将任意子表达式 ((AB)C) 改为 (A(BC)),其中 A,B,CA,B,C 都合法。操作只允许这个方向。

给定 ℓ\ell,将所有恰有 ℓ\ell 个 x 的合法表达式,按字符顺序 ( < x < ) 排成字典序,记为 S1,…,SNS_1,\ldots,S_N,其中

N=Cℓ−1=1ℓ(2ℓ−2ℓ−1).N=C_{\ell-1}=\frac1\ell\binom{2\ell-2}{\ell-1}.

再给定 1,…,N1,\ldots,N 的排列 pp。计算满足 i<ji<j 且能够从 SpjS_{p_j} 经过零次或多次操作得到 SpiS_{p_i} 的数对 (i,j)(i,j) 数量。

输入格式

第一行整数 ℓ\ell,1≤ℓ≤141\le\ell\le14。第二行 N=Cℓ−1N=C_{\ell-1} 个整数 p1,…,pNp_1,\ldots,p_N,构成 1,…,N1,\ldots,N 的排列。最大 N=742900N=742900。

输出格式

输出满足条件的数对数量。

样例

4
3 1 5 2 4
3

ℓ=4\ell=4 时依次为 (((xx)x)x)、((x(xx))x)、((xx)(xx))、(x((xx)x))、(x(x(xx)))。一次操作可以从1到2或3,从2到4,从3或4到5。计入的数对为 (1,2),(3,4),(3,5)(1,2),(3,4),(3,5)。