#S44M11T2. 分数(score)

分数(score)

分数(score)

【题目描述】 给定一个数组,a1,a2,…ana_{1}, a_{2}, \ldots a_{n} 。你每次可以选择两个位置 i,ji, j ,满足 1≤i<j≤n1 \leq i<j \leq n ,且满足:ai&aj=aia_{i} \& a_{j}=a_{i} 或 ai&aj=aja_{i} \& a_{j}=a_{j} 。其中&是二进制与运算。选择两个位置 i,ji, j 后,你可以获得 MAX{ai,ai+1,…,aj}M A X\left\{a_{i}, a_{i+1}, \ldots, a_{j}\right\}(即 (i,j)(i, j) 区间的最大值)的分数。

你可以选择任意多次,但是一个数对 (i,j)(i, j) 只能选择一次。问你最多能获得多少分数?

【输入格式】 从文件 score.in 中读入数据。 第一行一个正整数 nn 。 第二行 nn 个非负整数 aia_{i} 。

【输出格式】 输出到文件 score.out 中。 输出一行答案。

【样例 1 输入】

5
2 3 7 4 1

【样例 1 输出】

38

【样例 2】

见下发文件的 score/score2.in 与 score/score2.ans。

【样例 3】

见下发文件的 score/score3.in 与 score/score3.ans。

【样例 4】

见下发文件的 score/score4.in 与 score/score4.ans。

【样例 5】

见下发文件的 score/score5.in 与 score/score5.ans。

【数据范围与提示】

对于 100%的数据,n≤3×105,0≤ai<214n \leq 3 \times 10^{5}, 0 \leq a_{i}<2^{14} 。

数据点 nn 特殊性质
1 ~ 4 n≤103n \leq 10^{3} A
5 ~ 6 无
7 ~ 10 n≤3×105n \leq 3 \times 10^{5} A,B
11 ~ 13 B,C
14 ~ 16 A
17 ~ 19 B
20 ~ 21 C
22 ~ 25 无

特殊性质 A:对于所有的 i(i<n)i(i<n) ,满足 ai≤ai+1a_{i} \leq a_{i+1} 。 特殊性质 B:对于所有的 ii ,满足 ai≤25a_{i} \leq 2^{5} 。 特殊性质 C:对于所有的 ii ,满足 ai=2ka_{i}=2^{k} ,其中 kk 为非负整数。

附加文件