Après le premier jour du concours UJGOI, Martel a organisé une fête pour tous les participants. Il sait que pour le -ème participant, le niveau de bonheur est a_i si sa chanson préférée n'est pas jouée. Sinon, le niveau de bonheur est a_i+1. Le niveau total de tristesse est égal à b_1\oplus~ b_2\oplus \dots \oplus ~b_n où b_i est le niveau de bonheur du -ème participant.
Sakurako, en tant qu'organisatrice, souhaite minimiser le niveau total de tristesse des participants, alors elle vous demande quelle est la valeur minimale qu'il peut avoir, afin qu'elle puisse trouver les chansons que Martel doit jouer à la fête.
La première ligne contient un entier (1\le n\le 3\cdot 10^5) — le nombre de participants.
La deuxième ligne contient entiers a_i (0\le a_i\le 10^9) — le niveau de bonheur de chaque concurrent.
Affichez un seul entier, le niveau total de tristesse minimal possible.
Example 1
Example 2
Dans le premier test, nous pouvons jouer la chanson préférée des deuxième et troisième participants. Alors, les niveaux de bonheur sont :
le niveau de bonheur du premier participant est ;
le niveau de bonheur du deuxième participant est ;
le niveau de bonheur du troisième participant est ;
le niveau de bonheur du quatrième participant est .
Ainsi, le niveau total de tristesse est 4~\oplus~4~\oplus~2~\oplus~2=0
( points): a_i\le 1;
( points): pour tout , il existe un tel que a_i~=~2^k;
( points): pour tout , il existe un tel que a_i~=~2^k-1;
( points): a_i\le 16;
( points): n\le 1\,000;
( points): sans contraintes supplémentaires.