#include<bits/stdc++.h>
 
#define int long long
#define fi first
#define se second
 
using namespace std;
 
const int MAXN = 500005;
//const int MOD = 1e9 + 7;

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios_base :: sync_with_stdio(0);
    int n;
    cin >> n;
    int a[n];
    unordered_map<int, int> pos_last;
    int cnt[MAXN] = {}, pos_first[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
        pos_last[a[i]] = i;
    }
    multiset<int> st;
    int most_color[n];
    for (int i = n - 1; i >= 0; i--) {
        if (cnt[a[i]]) {
            st.erase(st.find(cnt[a[i]]));
        }
        cnt[a[i]]++;
        st.insert(cnt[a[i]]);
        most_color[i] = *st.rbegin();
    }
    for (int i = n - 1; i >= 0; i--) {
        pos_first[a[i]] = i;
    }
    vector<pair<int, int>> v;
    for (pair<int, int> p : pos_last) {
        v.push_back({p.se, p.fi});
    }
    sort(v.begin(), v.end());
    int k = (int)v.size();
    int dp[k];
    int max_dp[k];
    for (int i = 0; i < k; i++) {
        auto [pos, col] = v[i];
        int j = lower_bound(v.begin(), v.end(), pair<int, int>({pos_first[col], -1})) - v.begin() - 1;
        dp[i] = (j == -1 ? 0 : max_dp[j]) + cnt[col];
        max_dp[i] = max(dp[i], i ? max_dp[i - 1] : -1);
    }
    int mx = 0;
    for (int i = 0; i < k; i++) {
        int pos = v[i].fi;
        mx = max(mx, dp[i] + (pos == n - 1 ? 0 : most_color[pos + 1]));
    }
    cout << n - mx;
    return 0;
}
