Bike loves looking for the second maximum element in the sequence. The second maximum element in the sequence of distinct numbers x1,x2,…,xk (k>1) is such maximum element xj, that the following inequality holds: .
The lucky number of the sequence of distinct positive integers x1,x2,…,xk (k>1) is the number that is equal to the bitwise excluding OR of the maximum element of the sequence and the second maximum element of the sequence.
You’ve got a sequence of distinct positive integers s1,s2,…,sn (n>1). Let’s denote sequence sl,sl+1,…,sr as s[l..r] (1≤l<r≤n). Your task is to find the maximum number among all lucky numbers of sequences s[l..r].
Note that as all numbers in sequence s are distinct, all the given definitions make sence. Input
The first line contains integer n (1<n≤105). The second line contains n distinct integers s1,s2,…,sn (1≤si≤109). Output
Print a single integer — the maximum lucky number among all lucky numbers of sequences s[l..r]. Sample test(s) Input
5 5 2 1 4 3
Output
7
Input
5 9 8 3 5 7
Output
15
Note
For the first sample you can choose s[4..5]={4,3} and its lucky number is (4 xor 3)=7. You can also choose s[1..2].
For the second sample you must choose s[2..5]={8,3,5,7}.
先rmq预处理好最大值，然后枚举每一个数作为次大值的情况，二分往左往右分别找到第一个大于它的数，，然后取一个最大值就行
/*************************************************************************> File Name: CF-172-D.cpp> Author: ALex> Mail: zchao1995@gmail.com> Created Time: 2015年04月03日 星期五 13时48分52秒 ************************************************************************/;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double eps = 1e-15;LL;typedef pair <int, int> PLL;const int N = 100100;LL dp[N][20];int LOG[N];LL arr[N];void initLOG(){LOG[0] = -1;for (int i = 1; i <= 100000; ++i){LOG[i] = LOG[i – 1];LOG[i] += !(i & (i – 1));}}void initRMQ(int n){for (int i = 1; i <= n; ++i){dp[i][0] = arr[i];}for (int j = 1; j <= LOG[n]; ++j){for (int i = 1; i + (1 << j) – 1 <= n; ++i){dp[i][j] = max(dp[i][j – 1], dp[i + (1 << (j – 1))][j – 1]);}}}LL ST(int l, int r){int k = LOG[r – l + 1];return max(dp[l][k], dp[r – (1 << k) + 1][k]);}int main(){int n;while (~scanf(“%d”, &n)){LL ans = 0;for (int i = 1; i <= n; ++i){scanf(“%I64d”, &arr[i]);}initLOG();initRMQ(n);for (int i = 1; i <= n; ++i){int l = i + 1, r = n, mid;LL tmp = arr[i];while (l <= r){mid = (l + r) >> 1;LL maxs = ST(i + 1, mid);if (maxs >= arr[i]){tmp = maxs;r = mid – 1;}else{l = mid + 1;}}ans = max(ans, tmp ^ arr[i]);l = 1;r = i – 1;tmp = arr[i];while (l <= r){mid = (l + r) >> 1;LL maxs = ST(mid, i – 1);if (maxs > arr[i]){tmp = maxs;l = mid + 1;}else{r = mid – 1;}}ans = max(ans, tmp ^ arr[i]);}printf(“%I64d\n”, ans);}return 0;}
可偏偏。多么温柔，一出口便是相互指责和嘲讽。
