题目描述

给定一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$。

要求找到其中的一个连续子序列 $a_l, a_{l+1}, \ldots, a_r$，且这段连续子序列中所有元素的异或和（即 $a_l \oplus a_{l+1} \oplus \ldots \oplus a_r$）最大。

你需要输出连续子序列的最大异或和，以及对应的连续子序列的其实和结尾元素的下标 $l$ 和 $r$。

如果存在多个连续子序列具有最大的异或和，选择结尾元素下标 $r$ 最小的；如果 $r$ 也相同，则选择最短的（即 $l$ 最大的）。

输入格式

第一行，一个整数 $n$。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n$。

输出格式

输出共一行，包含三个整数，以空格分隔，分别表示连续子序列的最大的异或和，起始位置以及终止位置。

样例

5
1 0 5 4 2

6 4 5

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 1000, a_i \lt 2^{20}$
• 对于 $100\%$ 的数据，$1 \le n \le 10^5, 0 \le a_i \lt 2^{31}$