Problem D: 最优子序列

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：5 Solved：2

Description

取 m=16 给出长度为 n 的整数序列 a1a2...an(0≤ai<2m) 。对于一个二进制数 x 定义其分值 w(x) 为 x+popcnt(x) 其中popcnt(x) 表示 x 二进制表示中 1 的个数。对于一个子序列 b1b2...bk 定义其子序列分值 S 为 w(b1⊕b2)+w(b2⊕b3)+W(b3⊕b4)+...+w(bk−1⊕bk) 。其中 ⊕ 表示按位异或。对于空子序列规定其子序列分值为0。求一个子序列使得其子序列分值最大，输出这个最大值。

Input

输入第一行包含一个整数 n(1≤n≤40000)。接下来一行包含 n 个整数 a1,a2,...,an 。

Output

输出一行，该序列子序列中的最大分值。

Sample Input Copy 

5
1 2 3 4 5

Sample Output Copy