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

#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 bit[MAXN];
int leftPos[MAXN], lastPos[MAXN];
int cntCross[MAXN];

int lvs;
bool tree[1 << 18];

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);
    }
}

int solve() {
    int ans = 0;
    sz = 0;
    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 ++;

    return ans;
}

void brute() {
    int ans = 0;
    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;
}

void update(int idx, int val) {
    idx ++;
    while(idx <= n) {
        bit[idx] += val;
        idx += (idx & -idx);
    }
}

int getSum(int idx) {
    idx ++;
    int ret = 0;
    while(idx) {
        ret += bit[idx];
        idx -= (idx & -idx);
    }
    return ret;
}

int getSum(int le, int ri) {
    if(!le) return getSum(ri);
    return getSum(ri) - getSum(le - 1);
}

bool cmp(int a, int b) {
    if(cntCross[a] != cntCross[b]) return cntCross[a] > cntCross[b];
    return leftPos[a] < leftPos[b];
}

void init() {
    memset(leftPos, -1, sizeof(leftPos));
    memset(lastPos, -1, sizeof(lastPos));

    for(int i = 0; i < n; i ++) {
        if(leftPos[ a[i] ] == -1) {
            leftPos[ a[i] ] = i;
            lastPos[ a[i] ] = i;
            update(i, 1);
        }
        else {
            update(lastPos[ a[i] ], -1);
            cntCross[ a[i] ] = getSum(leftPos[ a[i] ], i);
            lastPos[ a[i] ] = i;
            update(i, 1);
        }
    }

    sort(vec.begin(), vec.end(), cmp);
}

void updateSegment(int idx, int le, int ri, int a, int b) {
    if(ri < a || b < le) return;

    if(a <= le && ri <= b) {
        tree[idx] = true;
        return;
    }

    int mid = (le + ri) >> 1;
    updateSegment(idx << 1, le, mid, a, b);
    updateSegment((idx << 1) + 1, mid + 1, ri, a, b);

    if(tree[idx << 1] || tree[(idx << 1) + 1]) tree[idx] = true;
}

bool calc(int idx, int le, int ri, int a, int b) {
    if(ri < a || b < le)
        return false;

    if(a <= le && ri <= b)
        return tree[idx];

    int mid = (le + ri) >> 1;
    return (calc(idx << 1, le, mid, a, b) || calc((idx << 1) + 1, mid + 1, ri, a, b));
}

int solve2() {
    int ans = 0;

    lvs = 1;
    while(lvs < n) lvs <<= 1;

    memset(tree, 0, sizeof(tree));

    for(int i = vec.size() - 1; i >= 0; i --) {
        if(calc(1, 0, lvs - 1, leftPos[ vec[i] ], lastPos[ vec[i] ]))
            ans ++;
        updateSegment(1, 0, lvs - 1, leftPos[ vec[i] ], lastPos[ vec[i] ]);
    }

    return ans;
}

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

    cout << min(t1, t2) << endl;

    return 0;
}
