#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;
}
inline int maxx(int a,int b) {
    if(a>b) return a;
    return b;
}
inline int minn(int a,int b) {
	if(a>b) return b;
	return a;
}
const ll MAXN=555555;
int n,cnt,a[MAXN],b[MAXN],nw[MAXN];
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);
	}
};
inline range merge(range a,range b) {
	return (range){a.l+b.l,a.r+b.r};
}
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 ;
		Update(1,1,n,p,n,(k-nw[p]));
		nw[p]=k;
	}
	int mx,mn;
	void QPOS(int t,int l,int r,int p) {
		if(l==r) {
			mx=nd[t].mx,mn=nd[t].mn;
			return ;
		}
		pushdown(t);
		int mid=(l+r)>>1;
		if(p<=mid) QPOS(lc,l,mid,p);
		else QPOS(rc,mid+1,r,p);
	}
	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) {
			if(nd[lc].mn>=mn&&nd[lc].mx<=mx);
			else Query(lc,l,mid,ll,rr);
		}
		if(rr>=mid+1) {
			if(nd[rc].mn>=mn&&nd[rc].mx<=mx);
			else Query(rc,mid+1,r,ll,rr);
		}
	}
	void init() {
		mx=-(n+1),mn=(n+1);
	}
	inline int qsum(int l,int r) {
		if(l>r) return 0;
		int sum=0;
		init();
		QPOS(1,1,n,r);
		sum+=mx;
		if(l!=1) {
			init();
			QPOS(1,1,n,l-1);
			sum-=mx;
		}
		return sum;
	}
	inline 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;
	}
	inline 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;
	}
	inline bool judge(int x,int l,int r) {
		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;
inline bool check(int num,int x) {
	int sz=p[num].size();
	for(register int i=0;i<sz;i++) {
		if(i<x) sgt.upd(p[num][i],0);
		else sgt.upd(p[num][i],1);
	}
	for(register 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);
	}
	return false;
}
void clear(int x) {
	int sz=p[x].size();
	for(register int i=0;i<sz;i++) sgt.upd(p[x][i],-1);
}
inline int solve() {
	sgt.build();
	int fans=1;
	for(register int i=1;i<=n;i++) nw[i]=1;
	for(register int i=1;i<=cnt;i++) {
		int sz=p[i].size();
		int l=fans+1,r=sz,ans=-1;
		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);
//		if(clock()/CLOCKS_PER_SEC>1.97) return fans;
	}
	return fans;
}
inline bool check1(int x) {
	sgt.build();
	for(register int i=1;i<=n;i++) nw[i]=1;
	for(register int i=1;i<=cnt;i++) {
		int sz=p[i].size();
		if(sz>=x) {
			for(register int j=0;j<x;j++) sgt.upd(p[i][j],0);
			for(register int l=0;l+x-1<sz;l++) {
				int r=l+x-1;
				sgt.upd(p[i][r],0);
				if(sgt.judge(x,p[i][l],p[i][r])) return true;
				sgt.upd(p[i][l],-1);
			} 
		}
		for(register int j=0;j<sz;j++) sgt.upd(p[i][j],-1);
	}
	return false;
}
int sequence(int N, std::vector<int> A) {
	n=N;
	for(register int i=1;i<=n;i++) a[i]=b[i]=A[i-1];
	sort(b+1,b+n+1);
    for(register int i=1;i<=n;i++) if(b[i]!=b[i-1]) mp[b[i]]=++cnt;
    for(register int i=1;i<=n;i++) {
    	a[i]=mp[a[i]];
    	p[a[i]].push_back(i);
    }
    if(cnt<=sqrt(N)) {
    	int l=1,r=n,ans=-1;
        while(l<=r) {
        	int mid1=(l+r)>>1;
        	int mid=(mid1+r)>>1;
        	if(check1(mid)) l=mid+1,ans=mid;
        	else r=mid-1;
    	}
    	return ans;
	}
    return solve();
}