Into Blocks (easy version) (Codeforces 1209G1)
Tags: Greedy, dsu

This is an easier version of the next problem. In this version, $$$q = 0$$$.A sequence of integers is called nice if its elements are arranged in blocks like in $$$[3, 3, 3, 4, 1, 1]$$$. Formally, if two elements are equal, everything in between must also be equal.Let's define difficulty of a sequence as a minimum possible number of elements to change to get a nice sequence. However, if you change at least one element of value $$$x$$$ to value $$$y$$$, you must also change all other elements of value $$$x$$$ into $$$y$$$ as well. For example, for $$$[3, 3, 1, 3, 2, 1, 2]$$$ it isn't allowed to change first $$$1$$$ to $$$3$$$ and second $$$1$$$ to $$$2$$$. You need to leave $$$1$$$'s untouched or change them to the same value.You are given a sequence of integers $$$a_1, a_2, \ldots, a_n$$$ and $$$q$$$ updates.Each update is of form "$$$i$$$ $$$x$$$" — change $$$a_i$$$ to $$$x$$$. Updates are not independent (the change stays for the future).Print the difficulty of the initial sequence and of the sequence after every update.

Input: The first line contains integers $$$n$$$ and $$$q$$$ ($$$1 \le n \le 200\,000$$$, $$$q = 0$$$), the length of the sequence and the number of the updates.The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 200\,000$$$), the initial sequence.Each of the following $$$q$$$ lines contains integers $$$i_t$$$ and $$$x_t$$$ ($$$1 \le i_t \le n$$$, $$$1 \le x_t \le 200\,000$$$), the position and the new value for this position.

Output: Print $$$q+1$$$ integers, the answer for the initial sequence and the answer after every update.


Sample Inputs:
5 0
3 7 3 7 3

10 0
1 2 1 2 3 1 1 1 50 1

6 0
6 6 3 3 4 4

7 0
3 3 1 3 2 1 2

Sample Outputs:
2

4

0

4

Solution (Python):
def solution():
    (n, _) = map(int, input().split())
    A = list(map(int, input().split()))
    cnt = [0] * (200000 + 10)
    f = [0] * (200000 + 10)
    for i in range(n):
        cnt[A[i]] += 1
        f[A[i]] = i
    res = 0
    pre = 0
    sum_val = 0
    mx = 0
    s = set()
    for i in range(len(A)):
        r = f[A[i]]
        if A[i] not in s:
            s.add(A[i])
            sum_val += cnt[A[i]]
            mx = max(mx, cnt[A[i]])
        pre = max(pre, r)
        if pre == i:
            res += sum_val - mx
            mx = 0
            sum_val = 0
    print(res)
solution()
exit(0)
(n, q) = map(int, input().split())
vals = list(map(int, input().split()))

def overlap(itv1, itv2):
    if itv1[1] < itv2[0] or itv1[0] > itv2[1]:
        return False
    return True

def merge(itv1, itv2):
    return (min(itv1[0], itv2[0]), max(itv1[1], itv2[1]))

def union(parent, k1, k2):
    p1 = find(k1)
    p2 = find(k2)
    parent[p2] = p1
    return p1

def find(parent, k):
    if parent[k] == k:
        return k
    ans = find(parent[k])
    parent[k] = ans
    return ans

def solution(vals):
    pos = {}
    for (i, v) in enumerate(vals):
        if v not in pos:
            pos[v] = [i, i, 1]
        else:
            pos[v][1] = i
            pos[v][2] += 1
    pos_more_than_one = {k: v for (k, v) in pos.items() if v[0] != v[1]}
    parent = {k: k for k in pos}
    parent_itvs = {k: pos[k][:2] for k in pos}
    for k1 in pos_more_than_one:
        for k2 in pos_more_than_one:
            if k1 != k2:
                if overlap(pos[k1], pos[k2]):
                    r = union(parent, k1, k2)
                    parent_itvs[r] = merge(parent_itvs[r], pos[k1])
                    parent_itvs[r] = merge(parent_itvs[r], pos[k2])
    roots = set()
    for k in pos_more_than_one:
        roots.add(find(parent, k))
    ans = 0
    for root in roots:
        total_len = parent_itvs[root][1] - parent_itvs[root][0] + 1
        max_child = 1
        for k in pos_more_than_one:
            if find(k) == root:
                max_child = max(max_child, pos[k][-1])
        ans += total_len - max_child
    print(ans)

Solution (Python):
from collections import defaultdict

def solution():
    (n, _) = map(int, input().split())
    A = list(map(int, input().split()))
    cnt = defaultdict(int)
    f = defaultdict(int)
    for i in range(n):
        cnt[A[i]] += 1
        f[A[i]] = i
    res = 0
    pre = 0
    sum_val = 0
    mx = 0
    s = set()
    for i in range(len(A)):
        r = f[A[i]]
        if A[i] not in s:
            s.add(A[i])
            sum_val += cnt[A[i]]
            mx = max(mx, cnt[A[i]])
        pre = max(pre, r)
        if pre == i:
            res += sum_val - mx
            mx = 0
            sum_val = 0
    print(res)
solution()
exit(0)
(n, q) = map(int, input().split())
vals = list(map(int, input().split()))

def overlap(itv1, itv2):
    if itv1[1] < itv2[0] or itv1[0] > itv2[1]:
        return False
    return True

def merge(itv1, itv2):
    return (min(itv1[0], itv2[0]), max(itv1[1], itv2[1]))

def union(parent, k1, k2):
    p1 = find(k1)
    p2 = find(k2)
    parent[p2] = p1
    return p1

def find(parent, k):
    if parent[k] == k:
        return k
    ans = find(parent[k])
    parent[k] = ans
    return ans

def solution(vals):
    pos = {}
    for (i, v) in enumerate(vals):
        if v not in pos:
            pos[v] = [i, i, 1]
        else:
            pos[v][1] = i
            pos[v][2] += 1
    pos_more_than_one = {k: v for (k, v) in pos.items() if v[0] != v[1]}
    parent = {k: k for k in pos}
    parent_itvs = {k: pos[k][:2] for k in pos}
    for k1 in pos_more_than_one:
        for k2 in pos_more_than_one:
            if k1 != k2:
                if overlap(pos[k1], pos[k2]):
                    r = union(parent, k1, k2)
                    parent_itvs[r] = merge(parent_itvs[r], pos[k1])
                    parent_itvs[r] = merge(parent_itvs[r], pos[k2])
    roots = set()
    for k in pos_more_than_one:
        roots.add(find(parent, k))
    ans = 0
    for root in roots:
        total_len = parent_itvs[root][1] - parent_itvs[root][0] + 1
        max_child = 1
        for k in pos_more_than_one:
            if find(k) == root:
                max_child = max(max_child, pos[k][-1])
        ans += total_len - max_child
    print(ans)

Solution (Python):
(n, q) = map(int, input().split())
sequence = list(map(int, input().split()))
dict_first_occur = {}
dict_last_occur = {}
dict_count = {}
for i in range(n):
    if sequence[i] not in dict_first_occur:
        dict_first_occur[sequence[i]] = i
    dict_last_occur[sequence[i]] = i
    if sequence[i] not in dict_count:
        dict_count[sequence[i]] = 0
    dict_count[sequence[i]] += 1
block = 0
max_count = 0
constants = 0
for i in range(n):
    if i == dict_first_occur[sequence[i]]:
        block += 1
    if i == dict_last_occur[sequence[i]]:
        block -= 1
    max_count = max(max_count, dict_count[sequence[i]])
    if block == 0:
        constants += max_count
        max_count = 0
print(n - constants)