#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

namespace fastIO{ 
	#define BUF_SIZE 1000000 
	#define ll long long 
	//fread->read 
	bool IOerror=0; 
	inline char nc(){ 
		static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE; 
		if (p1==pend){ 
			p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin); 
			if (pend==p1){IOerror=1;return -1;} 
			//{printf("IO error!\n");system("pause");for (;;);exit(0);} 
		} 
		return *p1++; 
	} 
	inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';} 
	inline void read(int &x){ 
		bool sign=0; char ch=nc(); x=0; 
		for (;blank(ch);ch=nc()); 
		if (IOerror)return; 
		if (ch=='-')sign=1,ch=nc(); 
		for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; 
		if (sign)x=-x; 
	} 
	inline void read(ll &x){ 
		bool sign=0; char ch=nc(); x=0; 
		for (;blank(ch);ch=nc()); 
		if (IOerror)return; 
		if (ch=='-')sign=1,ch=nc(); 
		for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; 
		if (sign)x=-x; 
	} 
	inline void read(double &x){ 
		bool sign=0; char ch=nc(); x=0; 
		for (;blank(ch);ch=nc()); 
		if (IOerror)return; 
		if (ch=='-')sign=1,ch=nc(); 
		for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; 
		if (ch=='.'){ 
			double tmp=1; ch=nc(); 
			for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0'); 
		} 
		if (sign)x=-x; 
	} 
	inline void read(char *s){ 
		char ch=nc(); 
		for (;blank(ch);ch=nc()); 
		if (IOerror)return; 
		for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch; 
		*s=0; 
	} 
	inline void read(char &c){ 
		for (c=nc();blank(c);c=nc()); 
		if (IOerror){c=-1;return;} 
	} 
	//getchar->read 
	inline void read1(int &x){ 
		char ch;int bo=0;x=0; 
		for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1; 
		for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar()); 
		if (bo)x=-x; 
	} 
	inline void read1(ll &x){ 
		char ch;int bo=0;x=0; 
		for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1; 
		for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar()); 
		if (bo)x=-x; 
	} 
	inline void read1(double &x){ 
		char ch;int bo=0;x=0; 
		for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1; 
		for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar()); 
		if (ch=='.'){ 
			double tmp=1; 
			for (ch=getchar();ch>='0'&&ch<='9';tmp/=10.0,x+=tmp*(ch-'0'),ch=getchar()); 
		} 
		if (bo)x=-x; 
	} 
	inline void read1(char *s){ 
		char ch=getchar(); 
		for (;blank(ch);ch=getchar()); 
		for (;!blank(ch);ch=getchar())*s++=ch; 
		*s=0; 
	} 
	inline void read1(char &c){for (c=getchar();blank(c);c=getchar());} 
	//scanf->read 
	inline void read2(int &x){scanf("%d",&x);} 
	inline void read2(ll &x){ 
		#ifdef _WIN32 
			scanf("%I64d",&x); 
		#else 
		#ifdef __linux 
			scanf("%lld",&x); 
		#else 
			puts("error:can't recognize the system!"); 
		#endif 
		#endif 
	} 
	inline void read2(double &x){scanf("%lf",&x);} 
	inline void read2(char *s){scanf("%s",s);} 
	inline void read2(char &c){scanf(" %c",&c);} 
	#undef BUF_SIZE 
}; 
using namespace fastIO; 

#define bit(x) (1<<(x))
#define F(j,x) (((j)>>(x))&1)
typedef pair<ll,ll> PLL;
const int N=5010000;
const int M=21;
const int inf=1<<30;
int n,a[N],ans=inf,bo[33];
int dis[(1<<M)+10];
int trans(int u,int b) {
	assert(!(u&bit(b)));
	int w=u&((1<<b)-1);
	if (w==0) return u^(1<<b);
	u^=1<<(31-__builtin_clz(w));
	return u^(1<<b);
}
const int B=50;
int nxt[N/B][M][M];
int pre[N][M];
int main() {
	read(n);
	rep(i,0,n) {
		//scanf("%d",&a[i]);
		read(a[i]);
		a[i]--;
	}
	dis[0]=-1;
	rep(i,1,1<<M) {
		dis[i]=-2;
	}
	int tB=(n-2)/B;
	rep(i,0,M) rep(j,i,M) nxt[tB+1][i][j]=tB+1;
	for (int i=tB;i>=0;i--) {
		int l=i*B,r=min(i*B+B-1,n-2);
		rep(x,0,M) rep(y,x,M) nxt[i][x][y]=nxt[i+1][x][y];
		for (int j=l;j<=r;j++) {
			int u=a[j],v=a[j+1];
			if (u>v) swap(u,v);
			nxt[i][u][v]=i;
		}
	}
	rep(i,0,n) {
		if (i==0) {
			rep(j,0,M) pre[i][j]=-1;
		} else {
			rep(j,0,M) pre[i][j]=pre[i-1][j];
		}
		pre[i][a[i]]=i;
	}
	rep(u,0,1<<M) if (dis[u]!=-2) {
		int w=dis[u];
		auto upd=[&](int x,int y) {
			dis[x]=max(dis[x],y);
		};
		int pt=0;
		rep(i,0,M) if (!(u&(1<<i))) bo[pt++]=i;
		int vv=tB+1,zz=w/B+1;
		rep(i,0,pt) rep(j,i,pt) vv=min(vv,nxt[zz][bo[i]][bo[j]]);
		int nv=n;
		if (vv<=tB) {
			int l=vv*B,r=min(vv*B+B-1,n-2);
			for (int j=l;j<=r;j++) if (!F(u,a[j])&&!F(u,a[j+1])) {
				nv=j;
				break;
			}
		}
		int r=min((w/B)*B+B-1,n-2);
		for (int j=w+1;j<=r;j++) if (!F(u,a[j])&&!F(u,a[j+1])) {
			nv=j;
			break;
		}
		if (nv>=n) {
			ans=min(ans,__builtin_popcount(u));
			continue;
		}
		upd(trans(u,a[nv+1]),nv+1);
		rep(i,0,pt) {
			int o=pre[nv][bo[i]];
			if (o>=w+1) upd(trans(u,bo[i]),o);
		}
		/*rep(j,w+1,nv+1) {
			if (u&bit(a[j])) continue;
			upd(trans(u,a[j]),j);
		}*/
	}
	printf("%d\n",ans);
}