P9236 [Lanqiao Cup 2023 NOI Qualifier A] Sum of XOR Sums

Given an array $A_i$, compute the XOR sum of every subarray and then sum up all these XOR sums. In other words, for every pair $L, R$ satisfying $1 \leq L \leq R \leq n$, compute the XOR of the elements from the $L$-th to the $R$-th in the array, and output the total sum of the results over all such $L, R$.

The first line contains an integer $n$. The second line contains $n$ integers $A_i$, separated by a single space.

Output one line containing an integer representing the answer.

#### Constraints For $30\%$ of the testdata, $n \leq 300$. For $60\%$ of the testdata, $n \leq 5000$. For all testdata, $1 \leq n \leq 10^5$, $0 \leq A_i \leq 2^{20}$. Translated by ChatGPT 5