Maximum Xor Secondary(單調棧好題)

Maximum Xor Secondary

?CodeForces - 280B?

Bike loves looking for the second maximum element in the sequence. The second maximum element in the sequence of distinct numbers?x₁,?x₂,?...,?x_k?(k?>?1)?is such maximum element?x_j, that the following inequality holds:?.The lucky number of the sequence of distinct positive integers?x₁,?x₂,?...,?x_k?(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?s₁,?s₂,?...,?s_n?(n?>?1). Let's denote sequence?s_l,?s_l?+?1,?...,?s_r?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?≤?10⁵). The second line contains?n?distinct integers?s₁,?s₂,?...,?s_n?(1?≤?s_i?≤?10⁹).

Output

Print a single integer — the maximum lucky number among all lucky numbers of sequences?s[l..r].

Examples

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}.

題意：給你一串數，問你這一串數的任意子串中的最大值和次大值的異或最大值為多少。

題解：

　　因為一個數可以是很多個區間的最大值，一個數也可以是很多個區間的次大值，所以我們可以以數為研究對象而非一個個區間。

　　第一種做法：

　　　　　　　　從前往后和從后往前各跑一遍單調棧，每次求的是以當前值為次大值，之前一個比它大的值為最大值，然后這兩個值異或。因為單調棧求的就是這個數向左或者向右找第一個比它大的值的位置。所以這個數的位置和棧頂元素的位置構成的區間中，這個數和棧頂元素就是該區間里的次大值和最大值。

附代碼：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
const int maxn=1e5+10;
int ans;
stack<int>s;
stack<int>s2;
int a[maxn];
int main()
{int n;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&a[i]);}for(int i=0;i<n;i++){while(!s.empty()&&a[s.top()]<a[i]){s.pop();}if(!s.empty())ans=max(ans,a[i]^a[s.top()]);s.push(i);}for(int i=n-1;i>=0;i--){while(!s2.empty()&&a[s2.top()]<a[i]){s2.pop();}if(!s2.empty()){ans=max(ans,a[i]^a[s2.top()]);}s2.push(i);}printf("%d\n",ans);return 0;
} 

第二種做法：

　　　　　 %大佬，思路差不多，只是只用求一遍單調棧就可以。從后往前求一遍單調棧然后記錄一下對于每一個值它右邊第一個比它大的值的位置。然后遍歷一遍，每次可以同時求出該數作為最大值和次大值的異或值。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
stack<int> s;
int r[maxn];
int a[maxn];
int main()
{int n,ans;scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&a[i]);for(int i=n-1;i>=0;i--){while(!s.empty()&&a[s.top()]<a[i])//找每個數右邊第一個比它大的數的下標 
        {s.pop();}if(s.empty()){r[i]=n;}else{r[i]=s.top();}s.push(i);}ans=0;int t;for(int i=0;i<n;i++){int j=i+1;while(j<n){t=a[i]^a[j];if(t>ans){ans=t;}if(a[j]>a[i]){break;}j=r[j];}} printf("%d\n",ans);return 0;
}

?