Fluffy Funny Tuzi (FFT) has \(N\) piles of carrot lining up in a line, the \(i^{th}\) of which has \(a_i\) carrots.
Tuzi wants as many carrots as possible. It can magically merge two adjacent piles \(a_{i}, a_{i+1}\) to produce a new pile with \((a_{i} \oplus a_{i+1}) + 1\) carrots. Here \(\oplus\) means binary xor.
Nevertheless, Tuzi does not want to think optimally. Everytime it will pick the pile with the least carrots, and merge it with one of its adjacent pile(s) so that the new pile has the maximum possible number of carrots.
- If multiple piles contain the least number of carrots, then the left-most such pile is chosen.
- If for the chosen pile there are two merge choices and both choices yield a pile with the same number of carrots, the the left adjacent pile is merged.
Tuzi will keep merging until there is only one pile of carrots. It wonders how many carrots it can eventually obtain.