Minimum Colours (Easy)
Source: codechef
Difficulty: 2050

Minimum Colours (Easy)
This is the easy version of the problem. The difference is that you remember all array elements correctly, and there is no$A_i = 0$. It is worth 40 points in Division 2, 3 and 4. It is non-scoreable in Division 1.
You have an array$A$of$N$integers -$A_1, A_2, ..., A_N$.
You can perform the following operation as many times as you want:
Choose$L, R$such that$1 \le L < R \le N$and$A_L = A_R$, then update$A_i := A_L$for all$L \le i \le R$.
Let$f(A)$denote the minimum number of distinct elements in the array$A$after applying operations optimally.
In this version of the problem, you remember all array elements correctly, and you just need to answer the value of$f(A)$for the given array.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of two lines of input.
The first line of each test case contains$N$- the size of the array.
The second line contains$N$integers -$A_1, A_2, ..., A_N$.
Output Format
For each test case, output on a new line the number of distinct elements.
Constraints$1 \le T \le 10^4$$3 \le N \le 2 \cdot 10^5$$1 \le A_i \le N$The sum of$N$does not exceed$2 \cdot 10^5$over all test cases.
Sample 1:
Explanation:
Test case$1$: Choose$L = 1, R = 3$and the array becomes$[1, 1, 1]$with only$1$distinct element.
Test case$2$: Do no operation. The array has$2$distinct elements. It is impossible to make it lower.

Sample Input:
4
3
1 2 1
4
1 2 1 2
6
1 2 1 2 3 2
3
1 2 3

Sample Output:
1
2
2
3

C++ solution:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#ifdef DEBUG
#include "cpplib/debug/debug.hpp"
#else
#define dbg(...)
#endif

#define SZ(x) (int) x.size()
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
#define REV(v) reverse(ALL(v))
#define SUM(v) accumulate(ALL(v), 0LL)
#define MAX(v) *max_element(ALL(v))
#define MAX_I(v) (max_element(ALL(v)) - v.begin())
#define MIN(v) *min_element(ALL(v))
#define MIN_I(v) (min_element(ALL(v)) - v.begin())
#define LB(v, x) lower_bound(ALL(v), (x)) - (v).begin()
#define UB(v, x) upper_bound(ALL(v), (x)) - (v).begin()
#define UNIQ(v) SORT(v), v.erase(unique(ALL(v)), v.end())
#define NXT_PER(v) next_permutation(ALL(v))
#define PREV_PER(v) prev_permutation(ALL(v))
#define CNT(v, x) count(ALL(v), (x))
#define FIND(v, x) find(ALL(v), (x)) - (v).begin()
#define DPRINT(y, x) cout << fixed << setprecision((x)) << (y) << '\n'

template<typename T> ostream &operator << (ostream &os, const vector<T> &A) { for (const auto &x : A) { os << x << ' '; }  return os;  }
template<typename T> istream &operator >> (istream &is, vector<T> &A) { for (auto &x : A) { is >> x; } return is; }
template <typename T> bool umax(T& a, const T& b) { if (a < b) { a = b; return true; }  return false; }
template <typename T> bool umin(T& a, const T& b) { if (a > b) { a = b; return true;  }  return false; }

template<class T> using pqmax = priority_queue<T>;
template<class T> using pqmin = priority_queue<T, vector<T>, greater<T>>;

void solve(int test) {
    int n; cin >> n;
    vector<int> a(n); for(auto &x: a) cin >> x;
    vector<int> dp(n); 
    vector<int> best(n + 1, n); 
    dp[0] = 1; 
    best[a[0]] = 0; 
    for(int i = 1; i < n; i++) {
        umin(best[a[i]], dp[i - 1]);
        dp[i] = 1 + best[a[i]];
    }
    cout << dp.back() << '\n';
}   

int main() {
    ios::sync_with_stdio(false); 
    cin.tie(nullptr); cout.tie(nullptr);

    int T = 1; 
    cin >> T;
    while(T--) {
        solve(T); 
    }   

    return 0;
}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

const INF = 1000000000

func main() {
    reader := bufio.NewReader(os.Stdin)
    writer := bufio.NewWriter(os.Stdout)
    defer writer.Flush()

    line, _ := reader.ReadString('\n')
    T, _ := strconv.Atoi(strings.TrimSpace(line))

    for ; T > 0; T-- {
        line, _ = reader.ReadString('\n')
        N, _ := strconv.Atoi(strings.TrimSpace(line))

        line, _ = reader.ReadString('\n')
        parts := strings.Fields(line)
        A := make([]int, N)
        for i := 0; i < N; i++ {
            A[i], _ = strconv.Atoi(parts[i])
        }

        dp := make([]int, N+1)
        for i := range dp {
            dp[i] = INF
        }
        dp[0] = 0

        bestFixed := make([]int, N+1)
        for i := range bestFixed {
            bestFixed[i] = INF
        }
        bestZero := INF

        for j := 1; j <= N; j++ {
            cur := A[j-1]

            if cur == 0 {
                bestZero = min(bestZero, dp[j-1])
                globalMin := bestZero

                for v := 1; v <= N; v++ {
                    globalMin = min(globalMin, bestFixed[v])
                }

                dp[j] = 1 + globalMin
            } else {
                bestFixed[cur] = min(bestFixed[cur], dp[j-1])
                dp[j] = 1 + min(bestZero, bestFixed[cur])
            }
        }

        fmt.Fprintln(writer, dp[N])
    }
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Java solution:
/*
                                            ██   ██ ██    ██ ███    ██  █████  ██
                                            ██  ██  ██    ██ ████   ██ ██   ██ ██
                                            █████   ██    ██ ██ ██  ██ ███████ ██
                                            ██  ██  ██    ██ ██  ██ ██ ██   ██ ██
                                            ██   ██  ██████  ██   ████ ██   ██ ███████
*/

import java.io.*;
import java.util.*;

public class Main {
    public static final int MOD = 1000000007;
    public static final int M = 998244353;
    public static final double eps = 1e-9;

    static PrintWriter out;
    static FastReader in;
    private static long lcm;

    public static void main(String[] args)throws Exception {
        in = new FastReader();
        out = new PrintWriter(System.out);
        int t = in.nextInt();
        while (t-- > 0) {
            solve();
            out.flush();
        }
    }

    public static void solve()throws Exception {
        int n = in.nextInt();
        int[] a = nextIntArray(n);
        int[] pos = new int[n+1];
        int[] dp = new int[n];
        Arrays.fill(pos,1000000000);
        dp[0]=1;
        pos[a[0]]=0;
        for(int i=1;i<n;i++){
            dp[i]=Math.min(dp[i-1]+1,pos[a[i]]+1);
            pos[a[i]]=Math.min(pos[a[i]],dp[i-1]);
        }
        out.println(dp[n-1]);
    }

    public static boolean check(ArrayList<Integer> ll){
        int n = ll.size();
        if(n==1) return true;
        for(int i=1;i<n;i++){
            if(ll.get(i)<=ll.get(i-1)) return false;
        }
        ArrayList<Integer> al = list();
        for(int i=1;i<n;i++){
            al.add(ll.get(i)-ll.get(i-1));
        }
        return check(al);
    }
    public static int end(){
        out.println("!");
        out.flush();
        return in.nextInt();
    }
    public static int query(int n) throws IOException {
        out.println(n);
        out.flush();
        return in.nextInt();
    }
    public static long power(long base, long exp) {
        long result = 1;
        base%=MOD;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = (result%MOD * base%MOD)%MOD;
            }
            base = (base%MOD * base%MOD)%MOD;
            exp >>= 1;
        }
        return result%MOD;
    }

    private static int[][] computePrefixSum(int[][] matrix, int n, int m) {
        int[][] prefixSum = new int[n + 1][m + 1]; // 1-based indexing for convenience

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                prefixSum[i][j] = matrix[i - 1][j - 1]
                        + prefixSum[i - 1][j]
                        + prefixSum[i][j - 1]
                        - prefixSum[i - 1][j - 1];
            }
        }
        return prefixSum;
    }

//    private static int[][] computeSubmatrixSums(int[][] prefixSum, int n, int m, int k) {
//        int resultRows = n - k + 1, resultCols = m - k + 1;
//        int[][] result = new int[resultRows][resultCols];
//
//        for (int i = 0; i < resultRows; i++) {
//            for (int j = 0; j < resultCols; j++) {
//                int x1 = i + 1, y1 = j + 1;
//                int x2 = i + k, y2 = j + k;
//
//                result[i][j] = prefixSum[x2][y2]
//                        - prefixSum[x1 - 1][y2]
//                        - prefixSum[x2][y1 - 1]
//                        + prefixSum[x1 - 1][y1 - 1];
//                result[i][j]=abs(k*k-2*result[i][j]);
//            }
//        }
//        return result;
//    }

    public static ArrayList<Integer> getDivisors(int n) {
        ArrayList<Integer> divisors = new ArrayList<>();
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                divisors.add(i);
                if (i != n / i) {
                    divisors.add(n / i);
                }
            }
        }
        return divisors;
    }
    public static long countInversions(int[] arr) {
        int[] temp = new int[arr.length];
        return mergeSortAndCount(arr, temp, 0, arr.length - 1);
    }
    private static long mergeSortAndCount(int[] arr, int[] temp, int left, int right) {
        int mid;long inversionCount = 0;
        if (left < right) {
            mid = (left + right) / 2;
            inversionCount += mergeSortAndCount(arr, temp, left, mid);
            inversionCount += mergeSortAndCount(arr, temp, mid + 1, right);
            inversionCount += mergeAndCount(arr, temp, left, mid, right);
        }
        return inversionCount;
    }

    private static long mergeAndCount(int[] arr, int[] temp, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int k = left;
        long inversions = 0;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
                inversions += (mid + 1 - i);
            }
        }
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        for (i = left; i <= right; i++) {
            arr[i] = temp[i];
        }
        return inversions;
    }
    //                                   ⠀⠀⠀⠀⠀⠀⣀⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
//                                   ⠀⠀⠀⢀⣴⣿⣿⠿⣟⢷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
//                                   ⠀⠀⠀⢸⣏⡏⠀⠀⠀⢣⢻⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
//                                   ⠀⠀⠀⢸⣟⠧⠤⠤⠔⠋⠀⢿⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
//                                   ⠀⠀⠀⠀⣿⡆⠀⠀⠀⠀⠀⠸⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
//                                   ⠀⠀⠀⠀⠘⣿⡀⢀⣶⠤⠒⠀⢻⣇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
//                                   ⠀⠀⠀⠀⠀⢹⣧⠀⠀⠀⠀⠀⠈⢿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
//                                   ⠀⠀⠀⠀⠀⠀⣿⡆⠀⠀⠀⠀⠀⠈⢿⣆⣠⣤⣤⣤⣤⣴⣦⣄⡀⠀⠀⠀⠀⠀⠀⠀
//                                   ⠀⠀⠀⠀⢀⣾⢿⢿⠀⠀⠀⢀⣀⣀⠘⣿⠋⠁⠀⠙⢇⠀⠀⠙⢿⣦⡀⠀⠀⠀⠀⠀
//                                   ⠀⠀⠀⢀⣾⢇⡞⠘⣧⠀⢖⡭⠞⢛⡄⠘⣆⠀⠀⠀⠈⢧⠀⠀⠀⠙⢿⣄⠀⠀⠀⠀
//                                   ⠀⠀⣠⣿⣛⣥⠤⠤⢿⡄⠀⠀⠈⠉⠀⠀⠹⡄⠀⠀⠀⠈⢧⠀⠀⠀⠈⠻⣦⠀⠀⠀
//                                   ⠀⣼⡟⡱⠛⠙⠀⠀⠘⢷⡀⠀⠀⠀⠀⠀⠀⠹⡀⠀⠀⠀⠈⣧⠀⠀⠀⠀⠹⣧⡀⠀
//                                   ⢸⡏⢠⠃⠀⠀⠀⠀⠀⠀⢳⡀⠀⠀⠀⠀⠀⠀⢳⡀⠀⠀⠀⠘⣧⠀⠀⠀⠀⠸⣷⡀
//                                   ⠸⣧⠘⡇⠀⠀⠀⠀⠀⠀⠀⢳⡀⠀⠀⠀⠀⠀⠀⢣⠀⠀⠀⠀⢹⡇⠀⠀⠀⠀⣿⠇
//                                   ⠀⣿⡄⢳⠀⠀⠀⠀⠀⠀⠀⠈⣷⠀⠀⠀⠀⠀⠀⠈⠆⠀⠀⠀⠀⠀⠀⠀⠀⣼⡟⠀
//                                   ⠀⢹⡇⠘⣇⠀⠀⠀⠀⠀⠀⠰⣿⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡄⠀⣼⡟⠀⠀
//                                   ⠀⢸⡇⠀⢹⡆⠀⠀⠀⠀⠀⠀⠙⠁⠀⠀⠀⠀⠀⠀⠀⠀⡀⠀⠀⠀⢳⣼⠟⠀⠀⠀
//                                   ⠀⠸⣧⣀⠀⢳⡀⠀⠀⠀⠀⠀⠀⠀⡄⠀⠀⠀⠀⠀⠀⠀⢃⠀⢀⣴⡿⠁⠀⠀⠀⠀
//                                   ⠀⠀⠈⠙⢷⣄⢳⡀⠀⠀⠀⠀⠀⠀⢳⡀⠀⠀⠀⠀⠀⣠⡿⠟⠛⠉⠀⠀⠀⠀⠀⠀
//                                   ⠀⠀⠀⠀⠈⠻⢿⣷⣦⣄⣀⣀⣠⣤⠾⠷⣦⣤⣤⡶⠟⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
//                                   ⠀⠀⠀⠀⠀⠀⠀⠈⠉⠛⠛⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀



    static long[] fact = new long[200005];
    static long[] inv = new long[200005];
    static int[][] lookup = new int[500][500];
    static int[][] gcdTable = new int[200005][20];



    public static Map<Integer, Integer> sortByValues(Map<Integer, Integer> map) {
        // Convert map entries to a list
        List<Map.Entry<Integer, Integer>> entryList = new ArrayList<>(map.entrySet());

        // Sort the list by values
        entryList.sort(Map.Entry.comparingByValue());

        // Create a LinkedHashMap to preserve insertion order
        Map<Integer, Integer> sortedMap = new LinkedHashMap<>();
        for (Map.Entry<Integer, Integer> entry : entryList) {
            sortedMap.put(entry.getKey(), entry.getValue());
        }

        return sortedMap;
    }

    public static int ceil(int x, int y){
        return x%y==0?x/y:x/y+1;
    }
    public static long ceil(long x, long y){
        return x%y==0?x/y:x/y+1;
    }
    //    public static int maxSubarraySum(int[] arr,int l,int r) {
//        int max_sum = 0;
//        int current_sum = 0;
//        for (int i = l; i <r; i++) {
//            current_sum = Math.max(arr[i], current_sum + arr[i]);
//            max_sum = Math.max(max_sum, current_sum);
//        }
//        return max_sum;
//    }
//
    public static int minSubarraySum(int[] arr,int l, int r) {
        int min_sum = 0;
        int current_sum = 0;
        for (int i = l; i <r; i++) {
            current_sum = Math.min(arr[i], current_sum + arr[i]);
            min_sum = Math.min(min_sum, current_sum);
        }
        return min_sum;
    }

//        static{
//        fact[0]=1;inv[0]=1;
//        for(int i=1;i<=2e5;i++){
//            fact[i]=fact[i-1]*i%MOD;
//            inv[i]=power(fact[i],MOD-2);
//        }
//    }
//    public static void minSparseTable(int[] a, int n){
//        for(int i=0;i<n;i++){
//            lookup[i][0]=a[i];
//        }
//        for(int j=1;(1<<j)<=n;j++){
//            for(int i=0;i+(1<<j)-1<n;i++){
//                lookup[i][j] = Math.min(lookup[i][j - 1], lookup[i + 1 << (j - 1)][j - 1]);
//            }
//        }
//    }
//
//    public static void gcdSparseTable(int[] a, int n){
//        for(int i=0;i<n;i++){
//            gcdTable[i][0]=a[i];
//        }
//        for(int j=1;j<20;j++){
//            for(int i=0;i+(1<<(j-1))<n;i++){
//                gcdTable[i][j]=gcd(gcdTable[i][j-1],gcdTable[i+(1<<(j-1))][j-1]);
//            }
//        }
//    }

    public static int log2(long N) {
        return 63 - Long.numberOfLeadingZeros(N);
    }
    public static long nCk(int n, int k) {
        if (k > n) return 0;
        return (fact[n] * inv[k] % MOD * inv[n-k] % MOD);
    }

    public static boolean binSearch(int[] arr, int key){
        int l = 0;
        int r = arr.length-1;
        while (l<=r){
            int mid = (l+r)/2;
            if (arr[mid]==key){
                return true;
            }
            if(arr[l]<arr[mid]){
                if (key>=arr[l]&&key<arr[mid]){
                    r=mid-1;
                }
                else {
                    l=mid+1;
                }
            }
            else {
                if (key>arr[mid]&&key<=arr[r]){
                    l=mid+1;
                }
                else {
                    r=mid-1;
                }
            }
        }
        return false;
    }


    public static int lower_bound(long[] arr,long key){
        int l = 0;
        int r = arr.length-1;
        int mid;
        while(r-l>1){
            mid = (r+l)/2;
            if(key>arr[mid]){
                l=mid+1;
            }
            else{
                r=mid;
            }
        }
        if(arr[l]>=key){
            return l;
        }
        else if(arr[r]>=key){
            return r;
        }
        return -1;
    }

    public static int upper_bound(long[] arr,long key){
        int l = 0;
        int r = arr.length-1;
        int mid;
        while(r-l>1){
            mid = (r+l)/2;
            if(key>=arr[mid]){
                l=mid+1;
            }
            else{
                r=mid;
            }
        }
        if(arr[l]>key){
            return l;
        }
        else if(arr[r]>key){
            return r;
        }
        return -1;
    }

    public static Integer lowerBound(TreeSet<Integer> set, int value) {
        return set.ceiling(value); // Returns the least element >= value
    }

    public static int lowerBound(List<Integer> list, int target) {
        int low = 0, high = list.size();
        while (low < high) {
            int mid = (low + high) / 2;
            if (list.get(mid) < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    public static int upperBound(List<Integer> list, int target) {
        int low = 0, high = list.size();
        while (low < high) {
            int mid = (low + high) / 2;
            if (list.get(mid) <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    public static int findIndex(int[] arr, int target) {
        int low = 0, high = arr.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (arr[mid] == target) {
                return mid; // Target found
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }
//    public static Pair<Integer,Integer> maxOcurrences(int[] arr) {
//        HashMap<Integer, Integer> frequencyMap = new HashMap<>();
//
//        // Count the frequency of each number
//        for (int num : arr) {
//            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
//        }
//
//        // Find the number with the highest frequency
//        int maxCount = 0;
//        int maxNumber = -1; // Default value (if the array is empty)
//        for (HashMap.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
//            if (entry.getValue() > maxCount) {
//                maxCount = entry.getValue();
//                maxNumber = entry.getKey();
//            }
//        }
//
//        return new Pair<>(maxNumber,maxCount);
//    }

    public static long abs(long a)
    {
        return Math.abs(a);
    }
    public static int abs(int a)
    {
        return Math.abs(a);
    }
    public static double abs(double a)
    {
        return Math.abs(a);
    }

    static long gcd(long a, long b){
        if(b==0){
            return a;
        }
        return gcd(b,a%b);
    }

//    static Boolean[] isPrime;
//    static{
//        int k = 10_000_010;
//        isPrime = new Boolean[k];
//        Arrays.fill(isPrime, true);
//        isPrime[0]=isPrime[1]=false;
//        for(int i=2;i<k;i++){
//            if(isPrime[i]){
//                for(int j=2*i;j<k;j+=i){
//                    isPrime[j]=false;
//                }
//            }
//        }
//    }

    static long exp(int a, int b){
        long ans = 1;
        long base = a;
        while(b>0){
            if((b&1)!=0){
                ans*=base;
            }
            base*=base;
            b>>=1;
        }
        return ans;
    }

    public static int max(int ... a)
    {
        int max = a[0];
        for (int i : a)
        {
            if (i > max)
            {
                max = i;
            }
        }
        return max;
    }

    public static long max(long ... a)
    {
        long max = a[0];
        for (long i : a) {
            if (i > max) {
                max = i;
            }
        }
        return max;
    }

    public static double max(double ... a)
    {
        double max = a[0];
        for (double i : a) {
            if (i > max) {
                max = i;
            }
        }
        return max;
    }

    // Minimum functions
    public static int min(int ... a)
    {
        int min = a[0];
        for (int i : a) {
            if (i < min) {
                min = i;
            }
        }
        return min;
    }

    public static long min(long ... a)
    {
        long min = a[0];
        for (long i : a) {
            if (i < min) {
                min = i;
            }
        }
        return min;
    }

    public static double min(double ... a)
    {
        double min = a[0];
        for (double i : a) {
            if (i < min) {
                min = i;
            }
        }
        return min;
    }

    public static boolean isSorted(long ar[])
    {
        int n=ar.length;
        for(int i=0;i<n-1;i++)
        {
            if(ar[i]>ar[i+1])return false;
        }
        return true;
    }


    public static int maxIntArray(ArrayList<Integer> ar)
    {
        int max=ar.get(0);
        for(int i=0;i<ar.size();i++)max=Math.max(max,ar.get(i));
        return max;
    }

    private static int countDigits(long l)
    {
        if (l >= 1000000000000000000L) return 19;
        if (l >= 100000000000000000L) return 18;
        if (l >= 10000000000000000L) return 17;
        if (l >= 1000000000000000L) return 16;
        if (l >= 100000000000000L) return 15;
        if (l >= 10000000000000L) return 14;
        if (l >= 1000000000000L) return 13;
        if (l >= 100000000000L) return 12;
        if (l >= 10000000000L) return 11;
        if (l >= 1000000000L) return 10;
        if (l >= 100000000L) return 9;
        if (l >= 10000000L) return 8;
        if (l >= 1000000L) return 7;
        if (l >= 100000L) return 6;
        if (l >= 10000L) return 5;
        if (l >= 1000L) return 4;
        if (l >= 100L) return 3;
        if (l >= 10L) return 2;
        return 1;
    }
    public static int minIntArray(ArrayList<Integer> ar)
    {

        int n=ar.size();
        int max=ar.get(0);
        for(int i=0;i<n;i++)max=Math.min(max,ar.get(i));
        return max;
    }
    public static int maxIntArray(int ar[])
    {
        int max=ar[0];
        for(int i=0;i<ar.length;i++)max=Math.max(max,ar[i]);
        return max;
    }

    public static int minIntArray(int ar[])
    {

        int max=ar[0];
        for(int i=0;i<ar.length;i++)max=Math.min(max,ar[i]);
        return max;
    }

    public static void endl()throws Exception
    {
        out.println();
    }
//    public static boolean isSorted(int ar[],int n)
//    {
//        if(n==1)return true;
//        int diff=ar[1]-ar[0];
//        for(int i=1;i<n;i++)
//        {
//            diff=Math.min(diff,ar[i]-ar[i-1]);
//        }
//        if(diff<0)return false;
//        return true;
//    }
//    public static boolean isSorted(Integer ar[],int n)
//
//    {
//        if(n==1)return true;
//        int diff=ar[1]-ar[0];
//        for(int i=1;i<n;i++)
//        {
//            diff=Math.min(diff,ar[i]-ar[i-1]);
//        }
//        if(diff<0)return false;
//        return true;
//    }

    // public static void addMap(TreeMap<Integer,Integer> map,Integer element)
    // {
    //     if(map.containsKey(element))
    //     map.put(element,map.get(element)+1);
    //     else map.put(element,1);
    // }


    public static <K> void removeMap(Map<K, Integer> map, K element)
    {
        if (!map.containsKey(element)) return;
        int currentCount = map.get(element);
        if (currentCount == 1) {
            map.remove(element);
        } else {
            map.put(element, currentCount - 1);
        }
    }

    public static <K> void addMap(Map<K, Integer> map, K element)
    {
        if (map.containsKey(element)) {
            map.put(element, map.get(element) + 1);
        } else {
            map.put(element, 1);
        }
    }

    // public static void addMap(TreeMap<Integer,Integer> map,Integer element)
    // {
    //     if(map.containsKey(element))
    //     map.put(element,map.get(element)+1);
    //     else map.put(element,1);
    // }
    public static void removeMap(TreeMap<Integer,Integer> map,int element)
    {
        if(map.get(element)==1)map.remove(element);
        else map.put(element,map.get(element)-1);
    }
    public static void removeMap(TreeMap<Long,Integer> map,long element)
    {
        if(!map.containsKey(element))return;
        if(map.get(element)==1)map.remove(element);
        else map.put(element,map.get(element)-1);
    }
    public static void removeMap(HashMap<Long,Integer> map,long element)
    {
        if(!map.containsKey(element))return;
        if(map.get(element)==1)map.remove(element);
        else map.put(element,map.get(element)-1);
    }
    public static void removeMap(HashMap<Integer,Integer> map,int element)
    {
        if(map.get(element)==1)map.remove(element);
        else map.put(element,map.get(element)-1);
    }

    public static void removeMap(HashMap<String,Integer> map,String element)
    {
        if(map.get(element)==1)map.remove(element);
        else map.put(element,map.get(element)-1);
    }
    // public static void addMap(TreeMap<Object,Integer> map,Integer element)
    // {
    //     if(map.containsKey(element))
    //     map.put(element,map.get(element)+1);
    //     else map.put(element,1);
    // }

    public static void addMap(TreeMap<Integer,Integer> map,Integer element)
    {
        if(map.containsKey(element))
            map.put(element,map.get(element)+1);
        else map.put(element,1);
    }

    public static void addMap(TreeMap<String,Integer> map,String element)
    {
        if(map.containsKey(element))
            map.put(element,map.get(element)+1);
        else map.put(element,1);
    }

    public static void addMap(TreeMap<Long,Integer> map,long element)
    {
        if(map.containsKey(element))
            map.put(element,map.get(element)+1);
        else map.put(element,1);
    }
    public static void addMap(HashMap<Integer,Integer> map,int element)
    {
        if(map.containsKey(element))
            map.put(element,map.get(element)+1);
        else map.put(element,1);
    }
    public static void addMap(HashMap<Long,Long> map,long element)
    {
        if(map.containsKey(element))
            map.put(element,map.get(element)+1);
        else map.put(element,1L);
    }
    public static void addMap(HashMap<Object,Integer> map,Integer element)
    {
        if(map.containsKey(element))
            map.put(element,map.get(element)+1);
        else map.put(element,1);
    }
    public static void addMap(HashMap<Long,Integer> map,Long element)
    {
        if(map.containsKey(element))
            map.put(element,map.get(element)+1);
        else map.put(element,1);
    }
    public static void addMap(HashMap<String,Integer> map,String element)
    {
        if(map.containsKey(element))
            map.put(element,map.get(element)+1);
        else map.put(element,1);
    }

    public static int[] nextIntArray(int n)throws Exception
    {
        int ar[]=new int[n];
        for(int i=0;i<n;i++)ar[i]=in.nextInt();
        return ar;
    }
    public static long[] nextlongArray(int n)throws Exception//For long
    {
        long ar[]=new long[n];
        for(int i=0;i<n;i++)ar[i]=in.nextLong();
        return ar;
    }
    public static Integer[] nextIntegerArray(int n)throws Exception
    {
        Integer ar[]=new Integer[n];
        for(int i=0;i<n;i++)ar[i]=in.nextInt();
        return ar;
    }
    public static Long[] nextLongArray(int n)//For Long array
    {
        Long ar[]=new Long[n];
        for(int i=0;i<n;i++)ar[i]=in.nextLong();
        return ar;
    }
    public static String[] nextStringArray(int n)
    {
        String ar[]=new String[n];
        for(int i=0;i<n;i++)ar[i]=in.next();
        return ar;
    }
    public long[][] nextLongMatrix(int height, int width){
        long[][] mat = new long[height][width];
        for(int h=0; h<height; h++) for(int w=0; w<width; w++){
            mat[h][w] = in.nextLong();
        }
        return mat;
    }
    public static int[][] nextIntMatrix(int height, int width){
        int[][] mat = new int[height][width];
        for(int h=0; h<height; h++) for(int w=0; w<width; w++){
            mat[h][w] = in.nextInt();
        }
        return mat;
    }

    public static char[][] nextCharMatrix(int height, int width){
        char[][] mat = new char[height][width];
        for(int h=0; h<height; h++){
            String s = in.next();
            for(int w=0; w<width; w++){
                mat[h][w] = s.charAt(w);
            }
        }
        return mat;
    }

    /*                                             OUTPUT PRINTING                                                              */
    public static void print(String s) {
        out.print(s);
    }

    public static <K, V> void debug(Map<K, V> map) {
        map.forEach((key, val) -> print(key + " : " + val + "\n"));
    }

    public static void debug(int... args) {
        for (int e : args)
            print(e + " ");
        print("\n");
    }

    public static void debug(long... arr) {
        for (long e : arr)
            print(e + " ");
        print("\n");
    }

    public static void debug(boolean... arr) {
        for (boolean e : arr)
            print(e + " ");
        print("\n");
    }

    public static void debug(char... arr) {
        for (char e : arr)
            print(e + " ");
        print("\n");
    }

    public static <T> void debug(List<T> list) {
        list.forEach(e -> print(e + " "));
        print("\n");
    }

    public static void debug(Object obj) {
        print(obj.toString() + "\n");
    }


    public static void Yes(boolean flag)throws Exception
    {
        if(flag)out.println("Yes");
        else  out.println("No");
    }
    public static void YES(boolean flag)throws Exception
    {
        if(flag)out.println("YES");
        else  out.println("NO");
    }
    public static void YES()throws Exception
    {
        out.println("YES");
    }
    public static void NO()throws Exception
    {
        out.println("NO");
    }
    public static void Yes()throws Exception
    {
        out.println("Yes");
    }
    public static void No()throws Exception
    {
        out.println("No");
    }


    public static void printArray(boolean ar[])throws Exception{
        for(boolean x:ar)out.print(x+" ");
        out.println();
    }
    public static void printArray(char ar[])throws Exception{
        for(char x:ar)out.print(x+" ");
        out.println();
    }

    public static void printArray(int ar[])throws Exception
    {
        for(int x:ar)out.print(x+" ");
        out.println();
    }
    public static void printArray(Object ar[])throws Exception
    {
        for(Object x:ar)out.print(x+" ");
        out.println();
    }
    public static void printArray(long ar[])throws Exception
    {
        for(long x:ar)out.print(x+" ");
        out.println();
    }


    static <T> ArrayList<T> Al(int n) {
        ArrayList<T> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            T element = (T) in.next();
            list.add(element);
        }
        return list;
    }

    static <K, V> HashMap<K, V> map() {
        return new HashMap<>();
    }
    static <T> ArrayList<T> list() {
        return new ArrayList<>();
    }
//    static <K, V> Pair<K, V> pair(K key, V value) {
//        return new Pair<>(key, value);
//    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }

    static class Pair<T extends Comparable<T>, U> implements Comparable<Pair<T, U>> {
        private final T first;
        private final U second;

        public Pair(T first, U second) {
            this.first = first;
            this.second = second;
        }

        public T first() {
            return first;
        }

        public U second() {
            return second;
        }

        @Override
        public int compareTo(Pair<T, U> other) {
            return this.first.compareTo(other.first);
        }

        @Override
        public String toString() {
            return "(" + first + ", " + second + ")";
        }
    }
}

JavaScript solution:
/* -------------------------------------------------------- */
/*   ( The Authentic JS CodeBuff )
 ___ _                      _              _ 
 | _ ) |_  __ _ _ _ __ _ __| |_ __ ____ _ (_)
 | _ \ ' \/ _` | '_/ _` / _` \ V  V / _` || |
 |___/_||_\__,_|_| \__,_\__,_|\_/\_/\__,_|/ |
                                        |__/ 
 */
/* ---------------------------------------------------------   */
/*    Youtube: https://youtube.com/@code-with-Bharadwaj        */
/*    Github : https://github.com/Manu577228                  */
/* ----------------------------------------------------------- */

const V8Flags = [
    '--max-old-space-size=4096', '--max-semi-space-size=16', '--stack-size=65536', '--reclaim-unused-memory',
    '--gc-interval=100', '--expose-gc', '--gc-global', '--optimize-for-speed',
    '--always-opt', '--max-inlined-source-size=600', '--max-inlined-bytecode-size=600', '--turbo-inline-js-wasm-calls',
    '--turbo', '--turbo-optimizer', '--force-optimization', '--no-lazy',
    '--no-lazy-inner-functions', '--optimize-for-size', '--initial-heap-size=64', '--max-heap-size=192',
    '--use-strict', '--predictable', '--single-threaded-gc', '--no-inline-new',
    '--opt', '--no-lazy-deserialization', '--no-browser-globals', '--turbo-inline-array-builtins',
    '--fast-math', '--fuzzing', '--minor-mc', '--incremental-marking',
    '--concurrent-recompilation', '--stress-compaction', '--experimental-flush-embedded-blob-icache', '--experimental-value-unavailable'
];

if (V8Flags.length > 0) {
        process.execArgv.push('--v8-options=' + V8Flags.join(' '));
}

const inputBuffer = Buffer.allocUnsafe(1e7);
let inputIndex = 0,
        inputLength = 0;
const outputBuffer = Buffer.allocUnsafe(1e7);
let outputIndex = 0;

const fs = require('fs');
inputLength = fs.readSync(process.stdin.fd, inputBuffer, 0, inputBuffer.length, null);

function readInt() {
        let num = 0,
                sign = 1;
        while (inputBuffer[inputIndex] < 48 || inputBuffer[inputIndex] > 57) {
                if (inputBuffer[inputIndex] === 45) sign = -1;
                inputIndex++;
        }
        while (inputIndex < inputLength && inputBuffer[inputIndex] >= 48 && inputBuffer[inputIndex] <= 57) {
                num = num * 10 + (inputBuffer[inputIndex++] - 48);
        }
        return num * sign;
}

let isFirstInLine = true;

function writeInt(value, isLast = false) {
        if (!isFirstInLine) {
                outputBuffer[outputIndex++] = 32;
        }
        if (value < 0) {
                outputBuffer[outputIndex++] = 45;
                value = -value;
        }
        let digits = [];
        do {
                digits.push(value % 10);
                value = Math.floor(value / 10);
        } while (value > 0);
        for (let i = digits.length - 1; i >= 0; i--) {
                outputBuffer[outputIndex++] = 48 + digits[i];
        }
        isFirstInLine = isLast;
        if (isLast) {
                outputBuffer[outputIndex++] = 10;
                isFirstInLine = true;
        }
}

let T = readInt();
while (T--) {
        let N = readInt();
        let A = new Array(N);
        for (let i = 0; i < N; i++) {
                A[i] = readInt();
        }
        let last = new Map();
        let dp = new Array(N + 1).fill(0);
        for (let i = N - 1; i >= 0; i--) {
                dp[i] = 1 + dp[i + 1];
                if (last.has(A[i])) {
                        dp[i] = Math.min(dp[i], dp[last.get(A[i])]);
                }
                last.set(A[i], i);
        }
        writeInt(dp[0], true);
}

fs.writeSync(process.stdout.fd, outputBuffer.slice(0, outputIndex));

Python solution:
def prog():
    t = int(input())
    for i in range(t):
        N = int(input())
        st = input().split()
        A = [0]
        for x in st:
            A.append(int(x))
        # endfor x
        B = [0 for x in range(N+1)]
        P = [N for x in range(N+1)]
        for k in range(1,N+1):
            n = A[k]
            v1 = B[k-1]
            v2 = P[n]
            v = min(v1,v2)
            B[k] = v+1
            P[n] = v
        # endfor k
        print (B[N])
    # endfor i
# end fun
prog()

Ruby solution:
def solve
  input = $stdin.read.split
  ptr = 0
  test_cases = input[ptr].to_i
  ptr += 1
  test_cases.times do
    n = input[ptr].to_i
    ptr += 1
    a = input[ptr, n].map(&:to_i)
    ptr += n
    
    dp = Array.new(n, 0)
    best = Array.new(n + 2, n + 1) # Initialize with a large value
    
    a.each_with_index do |val, i|
      if i > 0
        best[val] = [best[val], dp[i-1]].min
      else
        best[val] = 0
      end
      dp[i] = 1 + best[val]
    end
    
    puts dp[n-1]
  end
end

solve