codeforces#P1285D. Dr

    ID: 30805 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>bitmasksbrute forcedfs and similardivide and conquerdpgreedystringstrees*1900

Dr

Description

Today, as a friendship gift, Bakry gave Badawy nn integers a1,a2,,ana_1, a_2, \dots, a_n and challenged him to choose an integer XX such that the value max1in(aiX)\underset{1 \leq i \leq n}{\max} (a_i \oplus X) is minimum possible, where \oplus denotes the bitwise XOR operation.

As always, Badawy is too lazy, so you decided to help him and find the minimum possible value of max1in(aiX)\underset{1 \leq i \leq n}{\max} (a_i \oplus X).

The first line contains integer nn (1n1051\le n \le 10^5).

The second line contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (0ai23010 \le a_i \le 2^{30}-1).

Print one integer — the minimum possible value of max1in(aiX)\underset{1 \leq i \leq n}{\max} (a_i \oplus X).

Input

The first line contains integer nn (1n1051\le n \le 10^5).

The second line contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (0ai23010 \le a_i \le 2^{30}-1).

Output

Print one integer — the minimum possible value of max1in(aiX)\underset{1 \leq i \leq n}{\max} (a_i \oplus X).

Samples

输入数据 1

3
1 2 3

输出数据 1

2

输入数据 2

2
1 5

输出数据 2

4

Note

In the first sample, we can choose X=3X = 3.

In the second sample, we can choose X=5X = 5.