#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

Jianzhi was walking around in a garden one day, when he found a line of *N* ladybugs, each with a mysterious integer written onto it (what?). The *i*th ladybug from the front has the integer *A _{i}*. Through the use of his high-level experimental techniques, he managed to deduce that two ladybugs can only communicate with one another if the integers they carry have a bitwise

**AND**of 0.

He notices that if he randomly removes one ladybug from the line, the two ladybugs in front and behind it will come together and make the line complete again. Jianzhi would like to remove some ladybugs, such that any two adjacent ladybugs are able to communicate with one another, and he also wants to leave the maximum possible number of ladybugs in the line. Help Jianzhi find out what is the maximum number of ladybugs he can leave in the line.

## Limits

Subtask 1 (26%): 1 ≤ N ≤ 20, 0 ≤ A_{i} ≤ 10^{9}.

Subtask 2 (22%): 1 ≤ N ≤ 2000, 0 ≤ A_{i} ≤ 10^{9}. All A_{i} will be equal.

Subtask 3 (52%): 1 ≤ N ≤ 2000, 0 ≤ A_{i} ≤ 10^{9}.

Subtask 4 (0%): Sample Testcases

## Input

The first line of input will contain one integer, *N*.

The second line of input will contain *N* integers, representing the array *A*.

## Output

The output should contain exactly one integer, the maximum number of ladybugs Jianzhi can leave in the line.

## Sample Testcase 1

### Input

5 2 1 3 4 6

### Output

3

### Explanation

Jianzhi can leave the line [2, 1, 4].

## Sample Testcase 2

### Input

7 2 4 3 2 0 3 4

### Output

6

### Explanation

Jianzhi can leave the line [2, 4, 2, 0, 3, 4].

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 26 | 22 | 1s | 256MB | Minimum |

2 | 22 | 20 | 1s | 256MB | Minimum |

3 | 52 | 62 | 1s | 256MB | Minimum |

4 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o ladybugs -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512