حفلة UJGOI#411

حفلة UJGOI

ثانية
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;

  • ( نقاط): بدون قيود إضافية.