XOR Card Game

Interview

Time limit1sMemory limit1024 MB

Summary

Split the deck into consecutive groups of 2 or 3 cards to maximize the total count of 1 bits in each group's XOR. A leftover single card gives 0.

Level: Easy3 of 10
Topics: Dynamic programming, Bit manipulation
Solved: No attempts yet

Problem

In the XOR card game, a deck of $N$ cards is given. From the top, you take two or three cards at a time to earn points. Points accumulate through these steps:

XOR the numbers written on the cards taken at once.
Convert the value from step 1 to binary and earn one point for each 1 bit.

Watch out for one case. If a single card is left at the end, all points are lost and the game ends with 0 points. Find the maximum score that can be earned in this game.

Input

The first line contains the number of cards $N$ in the deck. $(1 \le N \le 100\,000)$

The second line contains the integers $A_1, A_2, \cdots, A_N$ written on each card, separated by spaces. $(2^0 \le A_i < 2^{10};$ $A_i$ is the number on the $i$ -th card from the top of the deck. $)$

Output

Print the maximum score that can be earned in this game.

Hint

For details on the bitwise XOR operator, see Wikipedia.

Examples3

Example 1
Input
```
5
2 1 3 8 4
```
Expected output
```
6
```
Example 2
Input
```
7
67 351 9 1023 497 261 1001
```
Expected output
```
18
```
Example 3
Input
```
1
5
```
Expected output
```
0
```