#include<bits/stdc++.h>
#define taskname "D"
using namespace std;
template<class T>bool minimize(T& a, T b){
if(a > b){
a = b;
return true;
}
return false;
}
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
const int lim = 5e6 + 5;
int n, a[lim];
namespace sub1{
void solve(){
int ans = n;
for(int mask = 0; mask < (1 << n); mask++){
bool flag = true;
for(int i = 1; i < n; i++){
if((mask >> i & 1) && (mask >> (i - 1) & 1)){
flag = false;
break;
}
}
if(flag){
for(int low = 1, high = ans - 1; low <= high; ){
int mid = (low + high) >> 1;
vector<int>cnt(22, 0);
cnt[1] = mid;
flag = true;
for(int i = 0; i < n; i++){
if((mask >> i & 1) == 0 && cnt[a[i + 1]] == 0){
flag = false;
for(int j = a[i + 1] - 1; j > 0; j--){
if(cnt[j] > 0){
cnt[j]--;
cnt[a[i + 1]]++;
flag = true;
break;
}
}
if(!flag){
break;
}
}
}
if(flag){
high = (ans = mid) - 1;
}
else{
low = mid + 1;
}
}
}
}
cout << ans;
}
}
namespace sub2{
const int lim = 505;
void solve(){
for(int i = 1; i < n; i++){
if(a[i] == 2 && a[i + 1] == 2){
for(int j = i + 2; j < n; j++){
if(a[j] == 1 && a[j + 1] == 1){
return void(cout << 2);
}
}
break;
}
}
cout << 1;
}
}
namespace sub34{
const int LIM = 1 << 15;
int dp[LIM][2], ndp[LIM][2];
void solve(){
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = dp[0][1] = 0;
for(int i = dp[1][0] = dp[1][1] = 1; i <= n; i++){
a[i]--;
memset(ndp, 0x3f, sizeof(ndp));
for(int mask = 0; mask < LIM; mask++){
ndp[mask][0] = dp[mask][1];
if(mask >> a[i] & 1){
int zmask = mask ^ (1 << a[i]);
ndp[mask][1] = min({dp[mask][0], dp[mask][1], min(dp[zmask][0], dp[zmask][1]) + 1});
for(int j = 0; j < a[i]; j++){
if((mask >> j & 1) == 0){
minimize(ndp[mask][1], min(dp[zmask | (1 << j)][0], dp[zmask | (1 << j)][1]));
}
}
}
}
memcpy(dp, ndp, sizeof(dp));
}
int ans = n;
for(int mask = 0; mask < LIM; mask++){
minimize(ans, min(dp[mask][0], dp[mask][1]));
}
cout << ans;
}
}
namespace sub5{
const int LIM = 1 << 15;
vector<int>p[15][15];
int dp[LIM];
int get_next(int v1, int v2, int x){
vector<int>::iterator it = upper_bound(p[v1][v2].begin(), p[v1][v2].end(), x);
return it == p[v1][v2].end() ? n + 1 : *it;
}
void solve(){
for(int i = 1; i < n; i++){
p[a[i] - 1][a[i + 1] - 1].push_back(i);
}
memset(dp, 0, sizeof(dp));
int ans = n;
for(int mask = 0; mask < LIM; mask++){
pair<int, int>np = make_pair(-1, -1);
int next_pos = n + 1;
for(int i = 0; i < 15; i++){
if((mask >> i & 1) == 0){
for(int j = 0; j < 15; j++){
if((mask >> j & 1) == 0 && minimize(next_pos, get_next(i, j, dp[mask]))){
np = make_pair(i, j);
}
}
}
}
if(np.first == -1){
minimize(ans, __builtin_popcount(mask));
}
else{
dp[mask] = next_pos - 1;
maximize(dp[mask | (1 << np.first)], next_pos);
maximize(dp[mask | (1 << np.second)], next_pos + 1);
for(int i = 0; i < np.first; i++){
if(mask >> i & 1){
maximize(dp[(mask ^ (1 << i)) | (1 << np.first)], next_pos);
}
}
for(int i = 0; i < np.second; i++){
if(mask >> i & 1){
maximize(dp[(mask ^ (1 << i)) | (1 << np.second)], next_pos + 1);
}
}
}
}
cout << ans;
}
}
namespace sub67{
vector<int>mask_by_len[22];
const int LIM = 1 << 21;
vector<int>p[21][21];
int dp[LIM], ptr[21][21];
void solve(){
for(int mask = 0; mask < LIM; mask++){
mask_by_len[__builtin_popcount(mask)].push_back(mask);
}
for(int i = 1; i < n; i++){
p[a[i] - 1][a[i + 1] - 1].push_back(i);
}
memset(dp, 0, sizeof(dp));
int ans = n;
for(int len = 0; len < 22; len++){
sort(mask_by_len[len].begin(), mask_by_len[len].end(), [&] (int i, int j){
return dp[i] < dp[j];
});
memset(ptr, 0, sizeof(ptr));
for(int& mask : mask_by_len[len]){
pair<int, int>np = make_pair(-1, -1);
int next_pos = n + 1;
for(int i = 0; i < 21; i++){
if((mask >> i & 1) == 0){
for(int j = 0; j < 21; j++){
if((mask >> j & 1) == 0){
while(ptr[i][j] < p[i][j].size() && p[i][j][ptr[i][j]] <= dp[mask]){
ptr[j][j]++;
}
if(minimize(next_pos, ptr[i][j] == p[i][j].size() ? n + 1 : p[i][j][ptr[i][j]])){
np = make_pair(i, j);
}
}
}
}
}
if((dp[mask] = next_pos - 1) == n){
return void(cout << len);
}
maximize(dp[mask | (1 << np.first)], next_pos);
maximize(dp[mask | (1 << np.second)], next_pos + 1);
for(int i = 0; i < np.first; i++){
if(mask >> i & 1){
maximize(dp[(mask ^ (1 << i)) | (1 << np.first)], next_pos);
}
}
for(int i = 0; i < np.second; i++){
if(mask >> i & 1){
maximize(dp[(mask ^ (1 << i)) | (1 << np.second)], next_pos + 1);
}
}
}
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
}
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
if(n <= 15){
sub1::solve();
}
else if(n <= 500 && *max_element(a + 1, a + n + 1) <= 2){
sub2::solve();
}
else if(n <= 500 && *max_element(a + 1, a + n + 1) <= 15){
sub34::solve();
}
else if(n <= 500000 && *max_element(a + 1, a + n + 1) <= 15){
sub5::solve();
}
else{
sub67::solve();
}
}
