Counting Operation Sequences to Sort a Permutation

Given a permutation (A) of the integers (1,2,\dots,2^N) (in other words, (A) is a rearrangement of the numbers from (1) to (2^N) ), you are allowed to take up to one operation of each of (N) types (in total at most (N) operations) in any order. For each (i) with (1\le i\le N), the (i\th) operation is defined as follows: partition the current sequence (from left to right) into (2^{N-i+1}) consecutive segments, each of length (2^{i-1}), and then choose any two distinct segments and swap them as whole blocks. Two operation sequences are considered different if they have different lengths or differ in at least one operation (either in the type or in the chosen segments to swap).

The task is to count the number of distinct operation sequences that will transform the given permutation (A) into sorted order (in increasing order). Note that you are not forced to use all available operations and an empty sequence (i.e. doing nothing) is a valid operation sequence if the array is already sorted.

For example, consider (N=3) and (A=[3,6,1,2,7,8,5,4]). One valid operation sequence is as follows:

• First, perform the 3rd operation (the only possibility for type 3): partition the array into \(2^{3-3+1}=2\) segments of length \(2^{3-1}=4\) and swap the two segments. The array becomes \([7,8,5,4,3,6,1,2]\).
• Then, perform the 1st operation: partition the array into \(2^{3-1+1} = 2^3=8\) segments of length \(2^{0}=1\) and choose a swap that swaps the elements at positions 3 and 5 (using 1-indexing). The array becomes \([7,8,3,4,5,6,1,2]\).
• Finally, perform the 2nd operation: partition the array into \(2^{3-2+1}=2^2=4\) segments of length \(2^{1}=2\) and choose a swap that exchanges the first and the last segments. After this, the array becomes \([1,2,3,4,5,6,7,8]\).

Your job is to count the number of distinct operation sequences (where each operation is specified by its type and the two segments chosen to swap) that will result in a sorted array. All formulas are given in LaTeX format.

inputFormat

The first line contains a single integer (N). The second line contains (2^N) space‐separated integers representing the permutation (A) of (1,2,\dots,2^N).

outputFormat

Output a single integer representing the number of distinct operation sequences that can sort the permutation in increasing order.

sample

1
1 2

1