Winning Segments

Time limit4sMemory limit256 MB

Summary

Given a permutation of 0..2^M-1, count the nonempty subarrays whose XOR can be made equal to 2^M-1 by one mandatory swap of two elements.

Level: Hard8 of 10
Topics: Bit manipulation, Prefix sum, Combinatorics, Array
Solved: No attempts yet

Problem

You are given an integer $M$ and an array $A$ of length $2^M$ that holds each of $0, 1, 2, \dots, 2^M - 1$ exactly once.

The computer picks one nonempty contiguous segment of $A$ . You then pick two different positions and swap the two numbers sitting there. The swap is mandatory, and the two positions may both lie inside the segment, both outside it, or one on each side. After the swap you win if the bitwise XOR of every number inside the segment the computer picked is exactly $2^M - 1$ .

The computer has $\frac{2^M(2^M+1)}{2}$ segments to pick from. Count how many of them let you win.

Input

The first line contains the integer $M$ ( $1 \le M \le 20$ ).

The second line contains the $2^M$ numbers of $A$ , separated by spaces. They form a permutation of $0, 1, 2, \dots, 2^M - 1$ .

Output

Print the number of segments that let you win, on one line.

Hint

In the first example, if the computer picks the segment 1 2 3, you win by swapping 0 and 3. In that example every segment except the whole array lets you win.

In the second example, if the computer picks the whole array 3 7 0 4 6 1 5 2, the XOR of the segment is 0 and swapping any two numbers leaves it at 0.

Examples3

Example 1
Input
```
2
0 1 2 3
```
Expected output
```
9
```
Example 2
Input
```
3
3 7 0 4 6 1 5 2
```
Expected output
```
33
```

Example 3

Input

4
13 0 15 12 4 8 7 3 11 14 6 10 1 5 9 2

Expected output