XOR Sequence

You are given an integer $N$ and a sequence $A$ of length $M$. $N$ is a power of two, and every element of $A$ is an integer between $0$ and $N-1$.

You may pick one integer $B$ between $0$ and $N-1$ and build a new sequence $C$. For every $i$, set $C_i = A_i \oplus B$, where $\oplus$ is bitwise exclusive or (XOR).

Then count the pairs $(i, j)$ with $i < j$ and $C_i < C_j$ in $C$.

Write a program that finds the largest possible number of such pairs over every choice of $B$.

The first line contains $N$. ($2 \le N \le 2^{30}$, $N$ is a power of two)

The second line contains the size $M$ of the sequence $A$. ($2 \le M \le 131072$)

The third line contains $A_1, A_2, \dots, A_M$ separated by spaces. ($0 \le A_i \le N-1$)

Print the largest possible number of pairs $(i, j)$ with $i < j$ and $C_i < C_j$.

For $N = 4$ and $A = [3, 2, 1, 0, 3, 2]$, choosing $B = 3$ gives $C = [0, 1, 2, 3, 0, 1]$. That sequence has 8 pairs with $i < j$ and $C_i < C_j$.