After the first day of the UJGOI contest, Martel made a party for all the contestants. He knows that for the -th participant, the happiness level is a_i if his favorite song is not played. Otherwise, the happiness level is a_i+1. The total sadness level equals b_1\oplus~ b_2\oplus \dots \oplus ~b_n where b_i is the happiness level of the -th participant.
Sakurako, as organizer, wants to minimize the total sadness level of participants, so she asks you what minimum value it can have, so she can find songs that Martel needs to play at the party.
The first line contains an integer (1\le n\le 3\cdot 10^5) — the number of participants.
The second line contains integers a_i (0\le a_i\le 10^9) — the happiness level of each contestant.
Output a single integer, the minimal possible total sadness level.
Example 1
Example 2
In the first test, we can play the favorite song of the second and third participants. Then, happiness levels are:
the first participant's happiness level is ;
the second participant's happiness level is ;
the third participant's happiness level is ;
the fourth participant's happiness level is .
So, the total sadness level is 4~\oplus~4~\oplus~2~\oplus~2=0
( points): a_i\le 1;
( points): for all exists such that a_i~=~2^k;
( points): for all exists such that a_i~=~2^k-1;
( points): a_i\le 16;
( points): n\le 1\,000;
( points): without additional constraints.