Bakry got bored of solving problems related to xor, so he asked you to solve this problem for him. You are given an array aa of nn integers [a1,a2,…,an][a1,a2,…,an]. Let’s call a subarray al,al+1,al+2,…,aral,al+1,al+2,…,ar good if al&al+1&al+2…&ar>al⊕al+1⊕al+2…⊕aral&al+1&al+2…&ar>al⊕al+1⊕al+2…⊕ar, where ⊕⊕ denotes the bitwise XOR operation and && denotes the bitwise AND operation. Find the length of the longest good subarray of aa, or determine that no such subarray exists.

Bored Bakry solution codeforces

Bakry got bored of solving problems related to xor, so he asked you to solve this problem for him.

You are given an array aa of nn integers [a1,a2,,an][a1,a2,…,an].

Let’s call a subarray al,al+1,al+2,,aral,al+1,al+2,…,ar good if al&al+1&al+2&ar>alal+1al+2aral&al+1&al+2…&ar>al⊕al+1⊕al+2…⊕ar, where  denotes the bitwise XOR operation and && denotes the bitwise AND operation.

Find the length of the longest good subarray of aa, or determine that no such subarray exists.

Bored Bakry solution codeforces

The first line contains a single integer nn (1n1061≤n≤106) — the length of the array.

The second line contains nn integers a1,a2,,ana1,a2,…,an (1ai1061≤ai≤106) — elements of the array.

Output

Print a single integer — the length of the longest good subarray. If there are no good subarrays, print 00.

Examples

input

Bored Bakry solution codeforces

2
5 6

output

Copy
2

Bored Bakry solution codeforces

Copy
3
2 4 3

output

Copy
0

input

Copy
6
8 1 3 3 1 2

output

Copy
4

Bored Bakry solution codeforces

In the first case, the answer is 22, as the whole array is good: 5&6=4>56=35&6=4>5⊕6=3.

In the third case, the answer is 44, and one of the longest good subarrays is [a2,a3,a4,a5][a2,a3,a4,a5]1&3&3&1=1>1331=01&3&3&1=1>1⊕3⊕3⊕1=0.

Leave a Reply

Your email address will not be published. Required fields are marked *

*