UJGOI Party#411

UJGOI Party

1 секунда
256 мегабайт
Very hard

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.

Input

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

Output a single integer, the minimal possible total sadness level.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

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

Scoring

  • ( 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.