奶牛异或

Adrian Vladu -- 2005

农夫约翰在喂奶牛时遇到了另一个问题。他的 N 头奶牛（1 ≤ N ≤ 100,000）编号为 1..N，按社会等级排成一排。1 号奶牛等级最高，N 号最低。每头奶牛还被分配了一个 0 到 2^21-1 之间的整数（不唯一）。

帮助 FJ 选择一组连续的奶牛，使得它们分配的数字的按位异或值最大。如果有多个这样的序列，选择最后一个奶牛等级最高的序列（即结束位置最靠后）。如果仍然并列，选择最短的序列。

时间限制：0.5 秒

程序名称：cowxor

输入格式

• 第一行：一个整数 N
• 第 2..N+1 行：N 个整数，范围 0 到 2^21-1，代表奶牛的分配数字。第 j 行描述社会等级为 j-1 的奶牛。

样例输入（文件 cowxor.in）

5
1
0
5
4
2

输入说明：

有 5 头奶牛。1 号分配 1，2 号 0，3 号 5，4 号 4，5 号 2。

输出格式

• 第一行：三个空格分隔的整数，分别是：最大异或值，序列的开始位置，序列的结束位置。

样例输出（文件 cowxor.out）

6 4 5

输出说明：

4 xor 2 = 6 (001) xor (010) = (011)