INFOMANIA 2023 round 1, educational edition | Xum

A fost odată o zână magică pe nume Ursul Brumi. Într-o zi, zâna a decis să se plimbe prin pădure, când, parcă de niciunde, o babă (@lavgiorgionicusor12 pe tik tok) a început să țipe la ea:

Am crezut că ai pățit ceva zânule. Ursul Brumi, am venit să te mănânc!

Odată ce a auzit acestea, Ursul Brumi a realizat că trebuie să se dezintegreze în mai multe bucăți pentru a deveni invizibil în fața babei. Astfel, el a scăpat de primejdie, iar, la final, s-a integrat înapoi într-o bucată, devenind, din nou, o zână de nota $10$.

Cerință

Se dă un vector $v$ de $N$ numere. Definim $xum(i \ldots j) = v_{i} \oplus v_{i+1} \oplus \ldots \oplus v_{j}$, unde $1 \leq i \leq j \leq N$, iar cu $\oplus$ am notat operatorul pe biți $xor^1$.
Calculați $S = \sum_{1 \leq i \leq j \leq n} xum(i \ldots j)$.

Date de intrare

Pe prima linie a fișierului xum.in se va afla $N$, numărul de elemente ale lui $v$. Pe următoarea linie, vor fi înșirate cele $N$ elemente ale lui $v$.

Date de ieșire

Afișați în fișierul xum.out rezultatul cerut.

Restricții și precizări

• $1 \leq N \leq 10^5$;
• $VMAX \leq 10^3$;
• $1 \leq v_{i} \leq VMAX$;
• $20\%$ din teste au $N \leq 10^3$;
• $^1$Despre operatorul "xor" puteți citi mai multe în acest articol foarte fin.

Exemplu

xum.in

3
1 2 3

xum.out

10

Explicație

$1 + 2 + 3 + (1 \oplus 2) + (2 \oplus 3) + (1 \oplus 2 \oplus 3) = 10$