1318: #2181. 「SDOI2015」排序

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

小 A 有一个 1∼2n 1 \sim 2 ^ n 12n 的排列 A[1…2n] A[1 \ldots 2 ^ n] A[12n],他希望将 A A A 数组从小到大排序,小 A 可以执行的操作有 n n n 种,每种操作最多可以执行一次,对于所有的 i i i1≤i≤n 1 \leq i \leq n 1in),第 i i i 种操作为将序列从左到右划分为 2n−i+1 2 ^ {n - i + 1} 2ni+1 段,每段恰好包括 2i−1 2 ^ {i - 1} 2i1 个数,然后整体交换其中两段。小 A 想知道可以将数组 A 从小到大排序的不同的操作序列有多少个,小 A 认为两个操作序列不同,当且仅当操作个数不同,或者至少一个操作不同(种类不同或者操作位置不同)。

下面是一个操作示例:n=3,A[1…8]=[3,6,1,2,7,8,5,4] n = 3, A[1 \ldots 8] = [3, 6, 1, 2, 7, 8, 5, 4] n=3,A[18]=[3,6,1,2,7,8,5,4]
第一次操作,执行第三种操作,交换 A[1…4] A[1 \ldots 4] A[14]A[5…8] A[5 \ldots 8] A[58],交换后的 A[1…8] A[1 \ldots 8] A[18][7,8,5,4,3,6,1,2] [7,8,5,4,3,6,1,2] [7,8,5,4,3,6,1,2]
第二次操作,执行第一种操作,交换 A[3] A[3] A[3]A[5] A[5] A[5],交换后的 A[1…8] A[1 \ldots 8] A[18][7,8,3,4,5,6,1,2] [7,8,3,4,5,6,1,2] [7,8,3,4,5,6,1,2]
第三次操作,执行第二种操作,交换 A[1…2] A[1 \ldots 2] A[12]A[7…8] A[7 \ldots 8] A[78],交换后的 A[1…8] A[1 \ldots 8] A[18][1,2,3,4,5,6,7,8] [1,2,3,4,5,6,7,8] [1,2,3,4,5,6,7,8]

输入格式

第一行一个整数 n n n
第二行 2n 2 ^ n 2n 个整数,表示 A[1…2n] A[1 \ldots 2 ^ n] A[12n]

输出格式

一个整数表示答案。

样例

样例输入

3
7 8 5 6 1 2 4 3

样例输出

6

数据范围与提示

1≤N≤12 1 \leq N \leq 12 1N12