No Two Alike
Source: codechef
Difficulty: 1801

No Two Alike
You are given an array$A$of length$N$. Your goal is to make all elements of$A$distinct. To achieve this, you can perform the following operation any number of times:
Select two indices$l$and$r$such that$1 ≤ l ≤ r ≤ |A|$. In the subarray$A [ l … r ]$, keep only the first occurrence of each element, and remove all subsequent repetitions of each element within this range.
The cost of performing this operation is number of distinct elements in initial subarray$A [ l … r ]$before doing this operation.
Your task is to calculate the
minimum
total cost required to make all elements of the final array$A$distinct.
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 number of elements in$A$.
The second line of each test case contains$N$space-separated integers$A_1, A_2, \ldots, A_N$, denoting the array$A$.
Output Format
For each test case, output on a new line the minimum total cost required to make all elements of the final array$A$distinct.
Constraints$1 \leq T \leq 10^5$$1 \leq N \leq 2\cdot 10^5$$1 \leq A_i \leq N$The sum of$N$over all test cases won't exceed$2\cdot 10^5$.
Sample 1:
Explanation:
Test case$2$:
We can perform the following operation:$[\underline{2, 2}] \xrightarrow{L = 1, R = 2} [2]$with cost$1$.
Test case$3$:
All the elements of$A$are already distinct.
Test case$4$:
One possible sequence of operations is as follows:$[1, 1, \underline{2, 3, 3, 2}] \xrightarrow{L = 3, R = 6} [1, 1, 2, 3]$with cost$2$.$[\underline{1, 1}, 2, 3] \xrightarrow{L = 1, R = 2} [1, 2, 3]$with cost$1$.
Total cost will be$3$. It can be shown that it's impossible to make all elements of this array distinct with less than total cost of$3$.

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

Sample Output:
0
1
0
3

C++ solution:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pair<int,int>>
#define pll pair<ll,ll>
#define pi pair<int,int>
#define Yarab_Accept ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define yes cout << "YES\n";
#define no cout << "NO\n";
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb emplace_back
#define pf push_front
#define test(n) while((n)--)
#define fi first
#define se second
#define input(a) for(auto&i:a)cin>>i
#define print(a) for(auto&i:a) cout << i << " "; cout << '\n'
#define mpi map<int,int>

void solve()
{
    int n; cin >> n;
    vi boundary(n + 1, -1), num(n+1,0);
    vi v(n);
    for(int i = 0 ; i < n; ++i)
    {
        cin >> v[i];
        boundary[v[i]] = i;
        num[v[i]]++;
    }
    int r = -1;
    unordered_map<int,int> freq;
    int cost = 0;
    for(int i = 0; i < n; ++i)
    {
        if(num[v[i]] <= 1 && i > r) continue;
        r = max(r, boundary[v[i]]);
        freq[v[i]] = 1;
        if(i == r)
        {
            cost += freq.size();
            freq.clear();
        }
    }
    cout << cost << '\n';
}
int main()
{
    Yarab_Accept
    int t = 1;
    cin >> t;
    test(t)solve();
    return 0;
}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "os"
)

type FastIO struct {
    scanner *bufio.Scanner
    writer  *bufio.Writer
}

func NewFastIO() *FastIO {
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Split(bufio.ScanWords)
    scanner.Buffer(make([]byte, 1024), 1024*1024)
    return &FastIO{
        scanner: scanner,
        writer:  bufio.NewWriter(os.Stdout),
    }
}

func (io *FastIO) ReadInt() int64 {
    io.scanner.Scan()
    num := int64(0)
    for _, ch := range io.scanner.Bytes() {
        num = num*10 + int64(ch-'0')
    }
    return num
}

func (io *FastIO) ReadArray(n int64) []int64 {
    arr := make([]int64, n)
    for i := int64(0); i < n; i++ {
        arr[i] = io.ReadInt()
    }
    return arr
}

func (io *FastIO) WriteInt(x int64) {
    fmt.Fprintln(io.writer, x)
}

func (io *FastIO) Flush() {
    io.writer.Flush()
}

type Processor struct {
    sequence []int64
    indices  map[int64]int64
    seen    map[int64]bool
}

func NewProcessor(sequence []int64) *Processor {
    indices := make(map[int64]int64)
    for i, v := range sequence {
        indices[v] = int64(i)
    }
    
    return &Processor{
        sequence: sequence,
        indices:  indices,
        seen:     make(map[int64]bool),
    }
}

func (p *Processor) Process() int64 {
    n := int64(len(p.sequence))
    endPos := int64(-1)
    result := int64(0)
    prevPos := int64(0)
    
    for i := int64(0); i < n; i++ {
        currVal := p.sequence[i]
        endPos = max(endPos, p.indices[currVal])
        p.seen[currVal] = true
        
        if endPos == i {
            if prevPos != i {
                result += int64(len(p.seen))
                p.seen = make(map[int64]bool)
            } else {
                p.seen = make(map[int64]bool)
            }
            prevPos = i + 1
        }
    }
    
    return result
}

func max(a, b int64) int64 {
    if a > b {
        return a
    }
    return b
}

func solve(io *FastIO) {
    n := io.ReadInt()
    sequence := io.ReadArray(n)
    
    processor := NewProcessor(sequence)
    result := processor.Process()
    
    io.WriteInt(result)
}

func main() {
    io := NewFastIO()
    defer io.Flush()
    
    t := io.ReadInt()
    for i := int64(0); i < t; i++ {
        solve(io)
    }
}

Java solution:
import java.util.*;
import java.io.*;

class Codechef {
    static long mod = 1000000007L;
    static final Random random = new Random();

    public static void main(String args[]) throws IOException {
        if(System.getProperty("ONLINE_JUDGE") == null){
            try {
                System.setIn(new FileInputStream("input.txt"));
                System.setOut(new PrintStream(new FileOutputStream("output.txt")));
            } catch (Exception e) {
                System.err.println("Error setting input/output files.");
                return; 
            }
        }

        FastReader in = new FastReader();
        int t = in.nextInt();
        while (t-- > 0) {
            int n = in.nextInt();
            int[] arr = in.readintarray(n);
            HashMap<Integer, Integer> map = new HashMap<>();
            
            // Store the last occurrence of each number
            for(int i = 0; i < n; i++){
                map.put(arr[i], i);
            }

            HashSet<Integer> seen = new HashSet<>();
            long ans = 0;

            for(int i = 0; i < n; i++){
                int j = map.getOrDefault(arr[i], i);
                //print("t:"+t+" i:"+i+"  j:"+j+" ans:"+ans);
                while(i < j && i < n) {
                    j = Math.max(j, map.getOrDefault(arr[i], i));
                    //print("t:"+t+" i:"+i+"  j:"+j+" ans:"+ans);
                    if(!seen.contains(arr[i])) {
                        seen.add(arr[i]);
                        ans++;
                    }
                    i++;
                }
            }
            print(ans);
        }
    }

    static <E> void print(E res) {
        System.out.println(res);
    }

    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());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        int[] readintarray(int n) {
            int res[] = new int[n];
            for (int i = 0; i < n; i++) res[i] = nextInt();
            return res;
        }
    }
}

JavaScript solution:
// your code goes here
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

function minCostToMakeDistinct(N, A) {
  let firstOccurrence = new Map(),
      lastOccurrence = new Map();

  for (let i = 0; i < N; i++) {
    if (!firstOccurrence.has(A[i])) firstOccurrence.set(A[i], i);
    lastOccurrence.set(A[i], i);
  }

  let uniquePositions = Array.from(lastOccurrence.values()).sort((a, b) => a - b);

  let distinctPrefix = Array(N).fill(0),
      distinctSuffix = Array(N).fill(0);

  let seen = new Set();
  for (let i = 0; i < N; i++) {
    seen.add(A[i]);
    distinctPrefix[i] = seen.size;
  }

  seen.clear();
  for (let i = N - 1; i >= 0; i--) {
    seen.add(A[i]);
    distinctSuffix[i] = seen.size;
  }

  let cost = 0,
      i = 0;

  while (i < A.length) {
    let j = i,
        maxPos = lastOccurrence.get(A[i]);

    while (j < A.length && j <= maxPos) {
      maxPos = Math.max(maxPos, lastOccurrence.get(A[j]));
      j++;
    }

    let currentCost = distinctPrefix[maxPos] - (i === 0 ? 0 : distinctPrefix[i - 1]);
    if (j - i !== currentCost) cost += currentCost;

    i = j;
  }

  return cost;
}

// Handle input
let inputLines = [],
    index = 0;

rl.on("line", (line) => {
  inputLines.push(line.trim());
}).on("close", () => {
  let T = parseInt(inputLines[index++], 10);
  let results = [];

  while (T--) {
    let N = parseInt(inputLines[index++], 10);
    let A = inputLines[index++].split(" ").map(Number);
    results.push(minCostToMakeDistinct(N, A));
  }

  console.log(results.join("\n"));
});

Python solution:
# eternal reverence to Shree DR.MDD
import sys

def analyze_cases(total_cases, data_batches):
    outcomes = []
    for case_id in range(total_cases):
        arr_len, sequence = data_batches[case_id]
        index_map = {}
        for pos, num in enumerate(sequence):
            if num not in index_map:
                index_map[num] = [pos, pos]
            else:
                index_map[num][1] = pos
        ranges = [(start, finish) for start, finish in index_map.values() if start < finish]
        if not ranges:
            outcomes.append(0)
            continue
        ranges.sort()
        merged = []
        l, r = ranges[0]
        for start, end in ranges[1:]:
            if start <= r:
                r = max(r, end)
            else:
                merged.append((l, r))
                l, r = start, end
        merged.append((l, r))
        final_sum = sum(len(set(sequence[start:end+1])) for start, end in merged)
        outcomes.append(final_sum)
    return outcomes

buffer = sys.stdin.read().split()
test_total = int(buffer[0])
batch_info = []
cursor = 1
for _ in range(test_total):
    length = int(buffer[cursor])
    elements = list(map(int, buffer[cursor + 1:cursor + 1 + length]))
    batch_info.append((length, elements))
    cursor += length + 1

sys.stdout.write("\n".join(map(str, analyze_cases(test_total, batch_info))) + "\n")

Ruby solution:
def solve
  testcases = gets.to_i
  testcases.times do
    n = gets.to_i
    values = gets.split.map(&:to_i)
    value_to_index = {}
    values.each_with_index do |val, idx|
      value_to_index[val] = idx
    end
    
    end_index = -1
    seen_values = {}
    result = 0
    previous_end = 0
    
    values.each_with_index do |val, idx|
      end_index = [end_index, value_to_index[val]].max
      seen_values[val] = true
      if end_index == idx
        if previous_end != idx
          result += seen_values.size
        end
        seen_values.clear
        previous_end = idx + 1
      end
    end
    
    puts result
  end
end

solve