#include <iostream>
#include <stdio.h>
#include <vector>
#include <string.h>

#define pb push_back

using namespace std;

const int MAXN = 100100;

int n, a[MAXN];
vector<int> vec;
bool inVec[MAXN];
vector<int> pos[MAXN];
int sz, idxList[MAXN], mn[MAXN];
int ans;

void read() {
    for(int i = 0; i < n; i ++) {
        scanf("%d", &a[i]);
        if(!inVec[ a[i] ]) {
            vec.pb(a[i]);
            inVec[ a[i] ] = true;
        }
        pos[ a[i] ].pb(i);
    }
}

void solve() {
    for(int i = 0; i < vec.size(); i ++) {
        for(int j = 0; j < pos[ vec[i] ].size(); j ++)
            idxList[sz ++] = pos[ vec[i] ][j];
    }

    mn[n - 1] = idxList[n - 1];
    for(int i = n - 2; i >= 0; i --)
        mn[i] = min(mn[i + 1], idxList[i]);

    for(int i = 0; i < n - 1; i ++)
        if(a[ idxList[i] ] != a[ idxList[i + 1] ] && mn[i + 1] < idxList[i])
            ans ++;

    cout << ans << endl;
}

void brute() {
    int x, le[32], ri[32];
    bool used[32], ma3x[32][32];
    int br = 0;

    memset(le, -1, sizeof(le));
    memset(ri, -1, sizeof(ri));
    memset(used, 0, sizeof(used));
    memset(ma3x, 0, sizeof(ma3x));

    for(int i = 1; i <= n; i ++) {
        scanf("%d", &x);
        x --;
        if(le[x] == -1) le[x] = i;
        ri[x] = i;
        if(!used[x]) br ++;
        used[x] = true;
    }

    for(int i = 0; i < n; i ++)
        for(int j = i + 1; j < n; j ++)
            if(le[i] != -1 && le[j] != -1) {
                if(le[i] > ri[j]) continue;
                if(ri[i] < le[j]) continue;
                ma3x[i][j] = ma3x[j][i] = true;
            }

    for(int mask = 0; mask < (1 << n); mask ++) {
        vector<int> cur;
        for(int i = 0; i < n; i ++)
            if(le[i] != -1 && ((mask >> i) & 1))
                cur.pb(i);

        bool fl = true;
        for(int i = 0; i < cur.size(); i ++)
            for(int j = i + 1; j < cur.size(); j ++)
                if(ma3x[ cur[i] ][ cur[j] ])
                    fl = false;
        if(fl) ans = max(ans, (int)cur.size());
    }
    cout << br - ans << endl;
}

int main()
{
    scanf("%d", &n);
    if(n <= 16) {
        brute();
        return 0;
    }
    read();
    solve();

    return 0;
}
