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 ith ladybug from the front has the integer Ai. 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 ≤ Ai ≤ 109.
Subtask 2 (22%): 1 ≤ N ≤ 2000, 0 ≤ Ai ≤ 109. All Ai will be equal.
Subtask 3 (52%): 1 ≤ N ≤ 2000, 0 ≤ Ai ≤ 109.
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].