事已至此，不如一起愉快地dp

#include <bits/stdc++.h>
#define int long long 
#define QAQ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'

using namespace std;
const int N=2e5+5,M=1e6+5;
int n,min_i,min_ai,minn=1e9;
int a[N],dp[N],b[M],c[M];//dp走到第i个格子最小步数 b标记数量 c标记上一个位置
signed main()
{//1.来自左边+1 2.来自上一个相同的+1 3.来自右边+1
	QAQ;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	dp[1]=0;
	minn=dp[1],min_i=1,min_ai=a[1];
	b[a[1]]=1,c[a[1]]=1;
	for(int i=2;i<=n;i++)
	{
		if(b[a[i]]>=1)//存在上一个
		{
			if(dp[i-1]>dp[c[a[i]]])//来自上一个
			{
				dp[i]=dp[c[a[i]]]+1;
				int num=i;
				while(dp[num-1]>dp[num]+1)//往前更新
				{
					dp[num-1]=dp[num]+1;
					num--;
				}
			}
			else
				dp[i]=dp[i-1]+1;//来自左
		}
		else
			dp[i]=dp[i-1]+1;//来自左
		b[a[i]]++;
		c[a[i]]=i;
	}
	
	cout<<dp[n];

	return 0;
}

#include<iostream>
#include<algorithm> 
#include<cstring>
#include<queue>

using namespace std;

typedef pair<int , int > PII ;
const int N = 200010, M = 3*N ;
int h[N] , e[M] , ne[M] , idx = 0 , n;
PII a[N] ;
int dis[N] ;
bool st[N] ;

void insert( int  a , int b)//wu
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++ ;
}

int bfs()
{
    memset (dis , -1 , sizeof dis ) ;
    dis [1] = 0 ;
    
    queue <int> q ;
    
    q.push(1) ;
    
    st[1] = true ;
    while(q.size())//bfs经典代码，路径最短的就会先到
    {
        auto t = q.front();
        q.pop() ;
        
        for(int i = h[t];i != -1;i = ne[i])
        {
            int j = e[i] ;
            if( !st[j] )
            {
                dis[j] = dis[t] + 1 ;
                q.push(j) ;
                st[j] = true ;
            }
        }    
    }
    return dis[n];
    
}



int main( )
{
    memset(h , -1 , sizeof h) ; 
    
    cin >> n ; 
    
    for( int i = 1;i <= n; i ++)cin >> a[i].first , a[i].second = i ; 
    
    sort(a + 1 , a + n + 1) ; 
    
    for( int i = 1 ; i < n ; i++) insert( i , i + 1 ) , insert( i + 1 , i ) ; //前后左右可移动一格，建立无向图 
    
    for(int i = 1 ; i < n ;  i ++) 
        if(a[i].first == a[i + 1].first) 
             insert(a[i].second , a[i + 1].second) ; //亮度相同正向瞬移建立树 
    
    cout << bfs();
    
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N=4000100;
int last[1000005];
int n,a[N],idx,cnt,e[N],ne[N],h[N];
bool vis[N];

void add (int x,int y)
{
	e[idx]=y,ne[idx]=h[x];h[x]=idx++;
	e[idx]=x,ne[idx]=h[y];h[y]=idx++;
}

void dxadd (int x,int y)
{
	e[idx]=y,ne[idx]=h[x];h[x]=idx++;
}

struct node
{
	int value;
	int cnt;
};

int bfs()
{
	vis[1]=1;
	queue<node> q;
	q.push({1,0});
	
	while(!q.empty())
	{
		node t=q.front();
		if(t.value==n) return t.cnt;
		q.pop();
		for(int i=h[t.value];i!=-1;i=ne[i])
		{
			int v=e[i];
			if(!vis[v])
			{
				vis[v]=1;
				q.push({v,t.cnt+1});
			}
		}
	}
}

int main()
{
	cin>>n;
	memset(h,-1,sizeof h);
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(i>1) add(i-1,i);
		if(last[a[i]]!=0) dxadd(last[a[i]],i);
		last[a[i]]=i;
	}
	cout<<bfs()<<endl;
}