题目描述
小 A 有一个 1∼2N 的排列 A1∼A2N,他希望将 A 数组从小到大排序,小 A 可以执行的操作有 N 种,每种操作最多可以执行一次,对于所有的 i(1≤i≤N),第 i 种操作为将序列从左到右划分为 2N−i+1 段,每段恰好包括 2i−1 个数,然后整体交换其中两段。
小 A 想知道可以将数组 A 从小到大排序的不同的操作序列有多少个。小 A 认为两个操作序列不同,当且仅当操作个数不同,或者至少一个操作不同(种类不同或者操作位置不同)。
下面是一个操作事例: N=3,A=[3,6,1,2,7,8,5,4]。
- 第一次操作,执行第 3 种操作,交换 A[1..4] 和 A[5..8],交换后的 A 为[7,8,5,4,3,6,1,2]。
- 第二次操作,执行第 1 种操作,交换 A[3] 和 A[5],交换后的 A 为[7,8,3,4,5,6,1,2]。
- 第三次操作,执行第 2 种操作,交换 A[1..2] 和 A[7..8],交换后的 A[1..8] 为[1,2,3,4,5,6,7,8]。
输入格式
第一行,一个整数 N。
第二行,2N 个整数,A1∼A2N。
输出格式
一个整数表示答案。
3
7 8 5 6 1 2 4 3
6
提示
100% 的数据, 1≤N≤12。