#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
inline ll read() {
	ll x=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int maxx(int a,int b) {
    if(a>b) return a;
    return b;
}
int minn(int a,int b) {
	if(a>b) return b;
	return a;
}
const ll MAXN=500005;
int n,cnt,a[MAXN],b[MAXN],nw[MAXN];
bool sg;
map <int,int> mp;
vector <int> p[MAXN];
struct range {
	int l,r;
	void add(int a) {
		l=minn(l,a),r=maxx(r,a);
	}
};
range merge(range a,range b) {
	return (range){a.l+b.l,a.r+b.r};
}
//int num=0;
struct SGTree {
	#define lc t<<1
	#define rc t<<1|1
	struct Node {
		int mx,mn,lz;
	}nd[4*MAXN];
	void pushup(int t) {
		nd[t].mx=maxx(nd[lc].mx,nd[rc].mx);
		nd[t].mn=minn(nd[lc].mn,nd[rc].mn);
	}
	void pushdown(int t) {
		if(nd[t].lz) {
			nd[lc].mn+=nd[t].lz;
			nd[rc].mn+=nd[t].lz;
			nd[lc].mx+=nd[t].lz;
			nd[rc].mx+=nd[t].lz;
			nd[lc].lz+=nd[t].lz;
			nd[rc].lz+=nd[t].lz;
			nd[t].lz=0;
		}
	}
	void Build(int t,int l,int r) {
		nd[t].lz=0;
		if(l==r) {
			nd[t].mx=nd[t].mn=l;
			return ;
		}
		int mid=(l+r)>>1;
		Build(lc,l,mid);
		Build(rc,mid+1,r);
		pushup(t);
	}
	void build() {
		Build(1,1,n);
	}
	void Update(int t,int l,int r,int ll,int rr,int k) {
		if(ll<=l&&r<=rr) {
			nd[t].mx+=k;
			nd[t].mn+=k;
			nd[t].lz+=k;
			return ;
		}
		pushdown(t);
		int mid=(l+r)>>1;
		if(ll<=mid) Update(lc,l,mid,ll,rr,k);
		if(rr>=mid+1) Update(rc,mid+1,r,ll,rr,k);
		pushup(t);
	}
	void upd(int p,int k) {
		if(nw[p]==k) return ;
//		num++;
		Update(1,1,n,p,n,(k-nw[p]));
		nw[p]=k;
	}
	int mx,mn;
	void Query(int t,int l,int r,int ll,int rr) {
		if(ll<=l&&r<=rr) {
			mx=maxx(mx,nd[t].mx);
			mn=minn(mn,nd[t].mn);
			return ;
		}
		pushdown(t);
		int mid=(l+r)>>1;
		if(ll<=mid) Query(lc,l,mid,ll,rr);
		if(rr>=mid+1) Query(rc,mid+1,r,ll,rr);
	}
	void init() {
		mx=-(n+1),mn=(n+1);
	}
	int qsum(int l,int r) {
//		num++;
		if(l>r) return 0;
		int sum=0;
		init();
		Query(1,1,n,r,r);
		sum+=mx;
		if(l!=1) {
			init();
			Query(1,1,n,l-1,l-1);
			sum-=mx;
		}
		return sum;
	}
	range qsuf(int x) {
		range ans=(range){0,0};
		if(!x) return ans;
		int sum=qsum(1,x);
		init();
		Query(1,1,n,1,x);
		ans.l=mn,ans.r=mx;
		ans.add(0);
		int tl=sum-ans.r,tr=sum-ans.l;
		ans.l=tl,ans.r=tr;
		return ans;
	}
	range qpre(int x) {
		range ans=(range){0,0};
		if(x==n+1) return ans;
		int sum=qsum(1,x-1);
		init();
		Query(1,1,n,x,n);
		ans.l=mn-sum,ans.r=mx-sum;
		ans.add(0);
		return ans;
	}
	bool judge(int x,int l,int r) {
		qpre(r+1);
		qpre(r+1);
		range nw=merge(qsuf(l-1),qpre(r+1));
		int sum=qsum(l,r);
		nw.l+=sum,nw.r+=sum;
		if(nw.r<=0) return x>=(-nw.r);
		if(nw.l>=0) return x>=nw.l;
		return 1;
	}
}sgt;
bool check(int num,int x) {
	int sz=p[num].size();
//	assert(x<=sz);
	for(int i=0;i<sz;i++) {
		if(i<x) sgt.upd(p[num][i],0);
		else sgt.upd(p[num][i],1);
	}
	for(int l=0;l+x-1<sz;l++) {
		int r=l+x-1;
		sgt.upd(p[num][r],0);
		if(sgt.judge(x,p[num][l],p[num][r])) return true;
		sgt.upd(p[num][l],-1);
	}
//	cout<<num<<' '<<x<<' '<<0<<'\n';
	return false;
}
void clear(int x) {
	int sz=p[x].size();
	for(int i=0;i<sz;i++) sgt.upd(p[x][i],-1);
}
int solve() {
	sgt.build();
	int fans=1;
	for(int i=1;i<=n;i++) nw[i]=1;
	for(int i=1;i<=cnt;i++) {
		int sz=p[i].size();
		int l=fans,r=sz,ans=-1;
		if(cnt) l++;
//		cout<<"!"<<l<<' '<<r<<'\n';
		while(l<=r) {
			int mid=(l+r)>>1;
			if(check(i,mid)) l=mid+1,ans=mid;
			else r=mid-1;
		}
		fans=max(fans,ans);
		clear(i);
	}
	return fans;
}
int sequence(int N, std::vector<int> A) {
	n=N;
	for(int i=1;i<=n;i++) a[i]=b[i]=A[i-1];
	sort(b+1,b+n+1);
    for(int i=1;i<=n;i++) if(b[i]!=b[i-1]) mp[b[i]]=++cnt;
    for(int i=1;i<=n;i++) {
    	a[i]=mp[a[i]];
    	p[a[i]].push_back(i);
	}
	sg=(cnt>sqrt(n));
    return solve();
}