UJGOI կուսակցություն#411

UJGOI կուսակցություն

1 վայրկյան
256 մեգաբայթ
Very hard

UJGOI մրցույթի առաջին օրվանից հետո, Մարտելը երեկույթ կազմակերպեց բոլոր մասնակիցների համար: Նա գիտի, որ -րդ մասնակիցի երջանկության մակարդակը a_i է, եթե նրա սիրելի երգը չի նվագվում: Այլապես, երջանկության մակարդակը a_i+1 է: Ընդհանուր տխրության մակարդակը հավասար է b_1\oplus~ b_2\oplus \dots \oplus ~b_n, որտեղ b_i-ը -րդ մասնակիցի երջանկության մակարդակն է:

Սակուրակոն, որպես կազմակերպիչ, ցանկանում է նվազեցնել մասնակիցների ընդհանուր տխրության մակարդակը, ուստի նա հարցնում է ձեզ, թե այն ինչ նվազագույն արժեք կարող է ունենալ, որպեսզի ինքը կարողանա գտնել այն երգերը, որոնք Մարտելը պետք է նվագի երեկույթի ժամանակ:

Input

Առաջին տողում տրված է (1\le n\le 3\cdot 10^5) ամբողջ թիվը՝ մասնակիցների քանակը:

Երկրորդ տողում տրված են ամբողջ a_i (0\le a_i\le 10^9) թվեր՝ մասնակիցների երջանկության մակարդակները:

Output

Արտածեք մեկ ամբողջ թիվ, նվազագույն հնարավոր ընդհանուր տխրության մակարդակը:

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

Առաջին թեստի մեջ, մենք կարող ենք նվագել երկրորդ և երրորդ մասնակիցների սիրելի երգերը: Այդ դեպքում, երջանկության մակարդակները կլինեն:

  • առաջին մասնակիցի երջանկության մակարդակը է;

  • երկրորդ մասնակիցի երջանկության մակարդակը է;

  • երրորդ մասնակիցի երջանկության մակարդակը է;

  • չորրորդ մասնակիցի երջանկության մակարդակը է.

Այսպիսով, ընդհանուր տխրության մակարդակը 4~\oplus~4~\oplus~2~\oplus~2=0 է:

Scoring

  • ( միավոր): a_i\le 1;

  • ( միավոր): բոլոր -երի համար կա այնպիսի , որ a_i~=~2^k;

  • ( միավոր): բոլոր -երի համար կա այնպիսի , որ a_i~=~2^k-1;

  • ( միավոր): a_i\le 16;

  • ( միավոր): n\le 1\,000;

  • ( միավոր): առանց լրացուցիչ սահմանափակումների.