← 返回题目列表

Codeforces · 1592/E

E. 无聊的巴克里

中文机器翻译题面 查看原题

Bakry 厌倦了解决与 xor 相关的问题,所以他请你帮他解决这个问题。

给定一个由 $$$n$$$ 整数 $$$[a_1, a_2, \ldots, a_n]$$$ 组成的数组 $$$a$$$。

我们称子数组 $$$a_{l}, a_{l+1}, a_{l+2}, \ldots, a_r$$$ 好,如果 $$$a_l \, \& \, a_{l+1} \, \& \, a_{l+2} \, \ldots \, \& \, a_r > a_l \oplus a_{l+1} \oplus a_{l+2} \ldots \oplus a_r$$$,其中$$$\oplus$$$表示按位异或运算,$$$\&$$$表示按位与运算。

求 $$$a$$$ 中最长的好子数组的长度,或者判断不存在这样的子数组。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — 数组的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — 数组的元素。

输出

打印一个整数——最长的好子数组的长度。如果没有好的子数组,则打印$$$0$$$。

示例

输入 #1

2
5 6

输出 #1

2

输入 #2

3
2 4 3

输出 #2

0

输入 #3

6
8 1 3 3 1 2

输出 #3

4

注意

在第一种情况下,答案是 $$$2$$$,因为整个数组都很好:$$$5 \& 6 = 4 > 5 \oplus 6 = 3$$$。

在第三种情况下,答案是 $$$4$$$,最长的好子数组之一是 $$$[a_2, a_3, a_4, a_5]$$$: $$$1\& 3 \& 3 \&1 = 1 > 1\oplus 3 \oplus 3\oplus 1 = 0$$$。