It is often effective to consider bitwise independently for a problem regarding XOR (exclusive logical sum).

For each \(j=0,1,\ldots,27\), define a sequence \(B\) of length \(N\) such that \(B_i=1\) if the \(j\)-th bit of \(A_i\) is \(1\) and \(B_i=0\) if it is \(0\). (Here, \(j\leq 27\) because \(\mathrm{MAX_A} = 10^8 < 2^{27}\).)

Solve the problem against \(B\) for each \(j\), and the total sum of the answers multiplied by \(2^j\) is the solution to the original problem.

This simplifies the problem as \(B\) takes only zero or one, as opposed to \(A\) taking variable values.

Next, the expression \(\sum_{i=1}^{N-1}\sum_{j=i+1}^N (B_i \oplus B_{i+1}\oplus \ldots \oplus B_j)\) requires the total XOR of a segment. This can be computed fast using cumulative XORs, just as utilizing cumulative sums when computing the total sum on a segment.

Specifically, define the array of cumulative XORs \(C\) by \(C_0=0\) and \(C_i =B_1\oplus \ldots \oplus B_i\).

Then we have the following equation: \(B_i \oplus B_{i+1}\oplus \ldots \oplus B_j = C_{i-1} \oplus C_j\). This helps us rewriting the expression to evaluate as follows:

\[ \sum_{i=1}^{N-1}\sum_{j=i+1}^N (C_{i-1} \oplus C_j) = \sum_{i=0}^{N-2}\sum_{j=i+2}^N (C_{i} \oplus C_j). \]

But it is troublesome that the index \(j\) starts from \(i+2\). Let us deform it to make it start from \(i+1\):

\[ \sum_{i=0}^{N-2}\sum_{j=i+2}^N (C_{i} \oplus C_j) = \sum_{i=0}^{N-1}\sum_{j=i+1}^N (C_{i} \oplus C_j) -\sum_{i=0}^{N-1} (C_i\oplus C_{i+1}) =\sum_{i=0}^{N-1}\sum_{j=i+1}^N (C_{i} \oplus C_j) - \sum_{i=1}^{N} B_i.\]

Now \(\sum_{i=0}^{N-1}\sum_{j=i+1}^N (C_{i} \oplus C_j)\) is the number of pairs of elements in \(C\) with different values, which turns out to be the product of the number of occurrences of \(0\) and that of \(1\) in \(C\).

Thus, the sought value can be simply evaluated with the total sum of \(B\) and the number of occurrences of \(0\) and \(1\) in the cumulative XORs. Hence, the problem has been solved in a total of \(\mathrm{O}(N\log {\mathrm{MAX_A}})\) time.