#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
bool flag[1<<17];
std::size_t n;
std::size_t data[1<<17];
std::size_t try_(){
    std::vector<std::list<std::size_t>::iterator> locations[1<<17];
    std::fill(flag, flag+n, false);
    std::list<std::size_t> g;
    for(std::size_t i=0;i<n;i++){
        g.push_back(data[i]);
        locations[data[i]].push_back(--g.end());
    }
    for(std::size_t i=0;i<n;i++){
        std::reverse(locations[i].begin(), locations[i].end());
        if(!locations[i].empty()) locations[i].pop_back();
    }
    std::size_t res=0;
    std::list<std::size_t>::iterator i=g.begin(), j;
    while(i!=g.end()){
        j=i++;
        if(flag[*j] || locations[*j].empty()) continue;
        if(locations[*j].back()!=i){
            flag[*j]=true;
            for(std::size_t k=0;k<locations[*j].size();++k){
                g.erase(locations[*j][k]);
            }
            locations[*j].clear();
        }else locations[*j].pop_back();
    }
    for(std::size_t i=0;i<n;i++){
        res+=flag[i];
    }
    return res;
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cin>>n;
    for(std::size_t i=0;i<n;i++){
        std::cin>>data[i];
        data[i]--;
    }
    std::size_t res=try_();
    std::reverse(data, data+n);
    std::size_t r=try_();
    if(r<res) res=r;
    std::cout<<res<<'\n';
    return 0;
}
