Winning Subsequence Swaps

You are given a positive integer M and a permutation of the numbers 0, 1, 2, \(\ldots, 2^M-1\). The target value is \(T = 2^M-1\). A computer selects a nonempty contiguous subsequence of the permutation and displays it. Then, you must choose two distinct elements anywhere in the permutation and swap their places. You win if and only if the bitwise XOR of the numbers (after the swap) in the lit contiguous subsequence is exactly \(T\).

Your task is to count the number of contiguous subsequences for which there exists a swap that guarantees a win.

Details:

• If the XOR of the chosen subsequence (denoted as \(X\)) is already equal to \(T\), then performing a swap completely inside the subsequence (or completely outside, if the subsequence is the whole array) will leave \(X\) unchanged and you win.
• If \(X\) is not equal to \(T\), then you can swap one element from the subsequence with an element from outside. Suppose you choose an element \(a\) in the subsequence. After the swap, \(a\) is replaced by an element \(b\) (which was originally outside the subsequence) and the new XOR becomes \(X \oplus a \oplus b\). To win, we require \[ X \oplus a \oplus b = T. \] This can be reformulated as \[ b = a \oplus (X \oplus T). \]
• The swap is valid if there exists at least one element \(a\) in the subsequence such that its corresponding \(b = a \oplus (X \oplus T)\) lies outside the boundaries of the chosen contiguous subsequence.

Count the number of contiguous subsequences for which a winning swap exists.

inputFormat

The first line contains a single integer M (M ≥ 1). The second line contains \(2^M\) distinct integers, which represent a permutation of \(0, 1, 2, \ldots, 2^M-1\).

outputFormat

Output a single integer — the number of contiguous subsequences for which there exists a swap that makes the bitwise XOR of the subsequence equal to \(2^M-1\).

sample

2
0 1 2 3

9