XOR cực đại thứ cấp (Maximum Xor Secondary)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy $s_1,s_2,\ldots,s_n$ gồm các số nguyên dương đôi một khác nhau. Với mỗi đoạn con liên tiếp có ít nhất hai phần tử, lấy phần tử lớn nhất và phần tử lớn thứ hai của đoạn, rồi tính XOR của hai giá trị đó. Hãy tìm giá trị XOR lớn nhất trên mọi đoạn hợp lệ.

Input

Dòng đầu chứa $n$. Dòng thứ hai chứa $n$ số nguyên đôi một khác nhau $s_1,s_2,\ldots,s_n$.

Output

In một số nguyên: giá trị XOR lớn nhất có thể.

Subtask

• Subtask 1 (30 điểm): $n\le2000$; các điều kiện khác giữ nguyên.
• Subtask 2 (70 điểm): $2\le n\le10^5$, $1\le s_i\le10^9$, các $s_i$ đôi một khác nhau.

Ví dụ

Input

5
5 2 1 4 3

Output

7

Giải thích

Dãy là $[5,2,1,4,3]$. Với mỗi đoạn có ít nhất hai phần tử, ta lấy hai giá trị lớn nhất rồi tính XOR.

Một số đoạn quyết định giá trị lớn nhất:

• Đoạn $[1..2]=[5,2]$: hai giá trị lớn nhất là $5$ và $2$, nên $5\oplus2=7$.
• Đoạn $[2..4]=[2,1,4]$: hai giá trị lớn nhất là $4$ và $2$, nên $4\oplus2=6$.
• Đoạn $[3..4]=[1,4]$: $4\oplus1=5$.
• Đoạn $[4..5]=[4,3]$: $4\oplus3=7$.
• Các đoạn dài chứa cả $5$ và $4$ có hai giá trị lớn nhất là $5$ và $4$, cho $5\oplus4=1$.

Không đoạn nào cho giá trị vượt quá $7$, trong khi các đoạn $[1..2]$ và $[4..5]$ đạt $7$. Vì vậy chương trình in 7.