#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
struct segmenttree{
	int n,e;function<int(int,int)> op;vector<int> v,flg;
	segmenttree(int n_,int e_,function<int(int,int)> op_,int coef):n(n_),e(e_),op(op_),v((n_+1)*4),flg((n_+1)*4){
		function<void(int,int,int)> build=[&](int id,int l,int r){
			if(l==r){v[id]=coef*l;return;}
			int md=l+r>>1;
			build(id<<1,l,md);build((id<<1)|1,md+1,r);
			v[id]=op(v[id<<1],v[(id<<1)|1]);
		};
		build(1,0,n);
	}
	inline void ad(int id,int val){v[id]+=val;flg[id]+=val;}
	inline void pushdown(int id){if(flg[id]) ad(id<<1,flg[id]),ad((id<<1)|1,flg[id]),flg[id]=0;}
	void modify(int id,int ql,int qr,int val,int l,int r){
		if(ql<=l&&r<=qr){ad(id,val);return;}
		pushdown(id);
		int md=l+r>>1;
		if(ql<=md) modify(id<<1,ql,qr,val,l,md);
		if(md<qr) modify((id<<1)|1,ql,qr,val,md+1,r);
		v[id]=op(v[id<<1],v[(id<<1)|1]);
	}
	int query(int id,int ql,int qr,int l,int r){
		if(ql<=l&&r<=qr) return v[id];
		pushdown(id);
		int md=l+r>>1;
		return op((ql<=md)?query(id<<1,ql,qr,l,md):e,(md<qr)?query((id<<1)|1,ql,qr,md+1,r):e);
	}
	void modify(int ql,int qr,int val){modify(1,ql,qr,val,0,n);}
	int query(int ql,int qr){return query(1,ql,qr,0,n);}
};
const int inf=1e6;
int sequence(int n,vector<int> a){
	vector<vector<int>> vec(n+1);int res=1;
	for(int i=0;i<n;++i) vec[a[i]].push_back(i+1);
	segmenttree T1(n,inf,[](int a,int b){return a<b?a:b;},1),T2(n,inf,[](int a,int b){return a<b?a:b;},-1);
	segmenttree T3(n,-1,[](int a,int b){return a>b?a:b;},1),T4(n,-1,[](int a,int b){return a>b?a:b;},-1);
	for(int i=1;i<=n;++i){
		for(auto p:vec[i]) T2.modify(p,n,2),T4.modify(p,n,2);
		auto chk=[&](int l,int r){
			return l>r||(T3.query(vec[i][r],n)>=T1.query(0,vec[i][l]-1)&&T4.query(vec[i][r],n)>=T2.query(0,vec[i][l]-1));
		};
		for(int sz=vec[i].size(),l=0,r=0;l<sz;res=max(res,r-l+1),++l) for(;r+1<sz&&chk(l,r+1);++r);
		for(auto p:vec[i]) T1.modify(p,n,-2),T3.modify(p,n,-2);
	}
	return res;
}