문제

Frograms, Inc. has been busy developing necklaces with brand-new design and feature. Every programmer working at Frograms now wears this necklace. A necklace consists of multiple beads stringed by a thread, as seen below. Each bead is given a number between 0 to 10⁹ (inclusive).

Most of the programmers have left for their summer vacation, and there is only a few programmers in the office today. So they decided to play a game using their own necklace to decide who will buy lunch for everyone. The rule is simple: for each pair of consecutive beads in the necklace, we take the XOR of their numbers. A programmer's score is defined as the sum of all those XOR values. The programmer with the lowest score loses! More formally, if there are N beads and their value is denoted by A₁, A₂, ..., A_N in the order they are stringed together, then the score is:

(A₁ xor A₂) + (A₂ xor A₃) + ... + (A_N-1 xor A_N) + (A_N xor A₁)

However, you, the most talented programmer in Frograms, Inc., is going to cheat the game by removing zero or more beads to maximize the score. What is the maximum score if you are allowed to remove some of the beads in a given necklace? Note that you cannot reorder the beads, nor leave one or less beads in a necklace.