#include <iostream>
#include <vector>
#include <ctime>
using namespace std;
struct node{
node* bit[2];
int cnt[2];
int i;
node(int b){
i = b;
bit[0] = bit[1] = NULL;
cnt[0] = cnt[1] = 0;
}
void insert(int n){
if (i==-1)
return;
bool b = (n&(1<<i));
if (bit[b]==NULL)
bit[b] = new node(i-1);
cnt[b]++;
bit[b]->insert(n);
}
int get(int k){
if (i==-1)
return 0;
if (cnt[0]>=k)
return bit[0]->get(k);
k -= cnt[0];
return (1<<i) + bit[1]->get(k);
}
void erase(int n){
if (i==-1)
return;
bool b = (n&(1<<i));
cnt[b]--;
bit[b]->erase(n);
}
};
int cnt[500005];
int opt2(int n,vector<int> v){
node* root = new node(20);
int ans = 0;
srand(time(0));
int K = 1e7 / n;
for (int k=0;k<K;k++){
int i = rand()%n;
for (int j=i;j<n;j++)
root->insert(v[j]),cnt[v[j]]++;
for (int j=n-1;j>=i;j--){
int k = j - i + 1;
ans = max(ans,cnt[root->get((k + 1) / 2)]);
if (k % 2 == 0)
ans = max(ans,cnt[root->get(k / 2 + 1)]);
root->erase(v[j]);
cnt[v[j]]--;
}
}
return ans;
}
int sequence(int n,vector<int> v){
if (n > 2000)
return opt2(n,v);
node* root = new node(20);
int ans = 0;
for (int i=0;i<n;i++){
for (int j=i;j<n;j++)
root->insert(v[j]),cnt[v[j]]++;
for (int j=n-1;j>=i;j--){
int k = j - i + 1;
ans = max(ans,cnt[root->get((k + 1) / 2)]);
if (k % 2 == 0)
ans = max(ans,cnt[root->get(k / 2 + 1)]);
root->erase(v[j]);
cnt[v[j]]--;
}
}
return ans;
}
// int main(){
// int n;
// cin>>n;
// vector<int> v(n);
// for (int i=1;i<=n;i++)
// cin>>v[i-1];
// cout<<sequence(n,v)<<endl;
// }
