题解 | #小红越级（hard）#

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1e9;
int main() {
    int n;cin>>n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    // dp[i] 表示清空前 i 个元素所需的最小操作次数
    // 初始化为 INF 表示不可达
    vector<int> dp(n + 1, INF);
    dp[0] = 0; // 清空 0 个元素不需要操作

    // min_prev[v] 记录数值 v 作为左端点时，其前一个位置的 DP 最小值
    // 即：min(dp[j-1]) for all j < i such that a[j] == v
    // 数值范围是 0 到 n，所以开 n+1 大小
    vector<int> min_prev(n + 1, INF);

    for (int i = 1; i <= n; ++i) {
        int val = a[i];

        // 1. 尝试计算 dp[i]
        // 如果之前出现过 val，我们可以与它配对，消除中间这一段
        // 代价是：消除 val 之前部分的代价 (min_prev[val]) + 本次操作 (1)
        if (min_prev[val] != INF) {
            dp[i] = min(dp[i], min_prev[val] + 1);
        }

        // 2. 更新 min_prev[val]
        // 将当前位置 i 视为未来可能的左端点。
        // 如果未来有一个 k (a[k] == val) 与 i 配对，那么剩下的就是清空 1...i-1 的代价。
        // 所以我们用 dp[i-1] 来更新 min_prev[val]
        if (dp[i-1] != INF) {
            min_prev[val] = min(min_prev[val], dp[i-1]);
        }
    }
    // 如果 dp[n] 仍然是 INF，说明无法清空数组
    if (dp[n] >= INF)cout << -1 << endl;
    else cout << dp[n] << endl;

    return 0;
}