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.


-----Examples-----
Input
5 0
3 7 3 7 3

Output
2

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

Output
4

Input
6 0
6 6 3 3 4 4

Output
0

Input
7 0
3 3 1 3 2 1 2

Output
4

Difficulty: competition

Starter code:

Solutions:
n, _q = map(int, input().split())
mni = [-1] * 200001
mxi = [-1] * 200001
cnt = [0] * 200001
nd = 0
a = list(map(int, input().split()))
for i, v in enumerate(a):
    if mni[v] == -1: mni[v] = i; nd += 1
    mxi[v] = i
    cnt[v] += 1
r = 0
z = 0
currmax = 0
for i, v in enumerate(a):
    if i == mni[v]: z += 1
    if i == mxi[v]: z -= 1
    currmax = max(currmax, cnt[v])
    if z == 0: r += currmax; currmax = 0
print(n - r)

from sys import stdin
n, q = tuple(int(x) for x in stdin.readline().split())

tpl = tuple(x for x in stdin.readline().split())

dic = {}
amt = {}
for i in range(n):
    dic[tpl[i]] = i
    if tpl[i] not in amt:
        amt[tpl[i]] = 1
    else:
        amt[tpl[i]] += 1

ans = 0
counter = 0
while counter < n:
    right_bound = dic[tpl[counter]]
    involved = set((tpl[counter],))
    counter += 1
    while counter < right_bound:
        if tpl[counter] not in involved:
            involved.add(tpl[counter])
            right_bound = max(right_bound, dic[tpl[counter]])
        counter += 1
    
    
    temp = tuple(amt[x] for x in involved)
    ans += sum(temp) - max(temp)
print(ans)


N, Q = list(map(int, input().split()))
A = [int(a) for a in input().split()]
B = sorted(list(set(A)))
M = len(B)
IA = {}
for i in range(M):
    IA[B[i]] = i

A = [IA[a] for a in A]
L = [N] * M
R = [-1] * M
C = [0] * M
for i in range(N):
    L[A[i]] = min(L[A[i]], i)
    R[A[i]] = max(R[A[i]], i)
    C[A[i]] += 1

X = []
for i in range(M):
    X.append((L[i], R[i], C[i]))
X = sorted(X, key = lambda x: x[1])

Y = [(-1, 0, 0)]
for i in range(M):
    l, r, t = X[i]
    m = t
    while Y[-1][0] > l:
        a, b, c = Y.pop()
        t += b
        m = max(m, c)
    Y.append((r, t, m))
print(sum([y[1] - y[2] for y in Y[1:]]))



import sys
input = sys.stdin.readline

n,q=list(map(int,input().split()))
A=list(map(int,input().split()))

if max(A)==min(A):
    print(0)
    return


L=max(A)

MM=[[200005,-1,i] for i in range(L+1)]
COUNT=[0]*(L+1)

for i in range(n):
    a=A[i]
    MM[a][0]=min(MM[a][0],i)
    MM[a][1]=max(MM[a][1],i)
    COUNT[a]+=1

MM.sort()

i,j,k=MM[0]

MAX=j
CC=COUNT[k]
MAXC=COUNT[k]
ANS=0

for i,j,k in MM[1:]:
    if i==200005:
        ANS+=CC-MAXC
        break
    
    if MAX<i:
        ANS+=CC-MAXC
        
        MAX=j
        CC=COUNT[k]
        MAXC=COUNT[k]

    else:
        CC+=COUNT[k]
        MAX=max(MAX,j)
        MAXC=max(MAXC,COUNT[k])

print(ANS)


n, q = map(int, input().split())
A = list(map(int, input().split()))
left = {}
right = {}
for i in range(n):
    if A[i] not in left:
        left[A[i]] = i
    right[A[i]] = i
E = []
for elem in left:
    E.append([left[elem], -1])
    E.append([right[elem], 1])
E.sort()
u = 0
b = 0
cntr = {}
ans = 0
for i in range(n):
    while u < len(E) and E[u][0] == i:
        b -= E[u][1]
        u += 1
    if A[i] not in cntr:
        cntr[A[i]] = 0
    cntr[A[i]] += 1
    if b == 0:
        s = 0
        m = 0
        for iss in cntr:
            s += cntr[iss]
            m = max(m, cntr[iss])
        ans += s - m
        cntr = {}
print(ans)

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    a = LI()
    a.sort()
    f = [1]*n
    p = 0
    ans = 0
    while p < n:
        while p < n and not f[p]:
            p += 1
        if p == n:
            break
        ans += 1
        for i in range(n):
            if a[i]%a[p] == 0:
                f[i] = 0
    print(ans)
    return

#B
def B():
    n = I()
    s = list(map(int, input()))
    g = LIR(n)
    ans = sum(s)
    for t in range(30000):
        for i in range(n):
            ai,bi = g[i]
            if t < bi:
                continue
            if (t-bi)%ai == 0:
                s[i] ^= 1
        su = sum(s)
        if ans < su:
            ans = su
    print(ans)
    return

#C
def C():
    t = I()
    for _ in range(t):
        n = I()
        s = list(map(int, input()))
        mi = [s[-1]]
        for i in range(n-1)[::-1]:
            mi.append(min(mi[-1],s[i]))
        mi = mi[::-1]
        ans = [None]*n
        for i in range(n):
            if mi[i] == s[i]:
                ans[i] = 1
            else:
                ans[i] = 2
        q = [s[i] for i in range(n) if ans[i] > 1]
        p = [q[i] for i in range(len(q))]
        p.sort()
        if p == q:
            for i in ans:
                print(i,end = "")
            print()
        else:
            print("-")
    return

#D
def D():
    def root(x):
        if x == par[x]:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

    n,k = LI()
    par = [i for i in range(n)]
    rank = [0]*n
    for i in range(k):
        x,y = LI()
        x -= 1
        y -= 1
        if root(x) != root(y):
            unite(x,y)
    size = [0]*n
    for i in range(n):
        size[root(i)] += 1
    ans = 0
    for i in size:
        if i > 0:
            ans += i-1
    print(k-ans)
    return

#E
def E():
    t = I()
    for _ in range(t):
        n,m = LI()
        s = LIR(n)
        s = [[s[i][j] for i in range(n)] for j in range(m)]
        if n <= m:
            ma = [max(s[i]) for i in range(m)]
            ma.sort(reverse = True)
            print(sum(ma[:n]))
        else:
            ans = 0
            k = [[]]
            for _ in range(m):
                k_ = []
                for i in range(n):
                    k_ += [x+[i] for x in k]
                k = [x for x in k_]
            for l in k:
                s_ = [[s[i][(j+l[i])%n] for j in range(n)] for i in range(m)]
                print(l)
                p = sum([max([s_[i][j] for i in range(m)]) for j in range(n)])
                print(s_,p)
                if ans < p:
                    ans = p
            print(ans)
    return

#F
def F():

    return

#G
def G():
    def root(x):
        if x == par[x]:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

    m = 200000
    par = [i for i in range(m)]
    rank = [0]*m
    n,q = LI()
    a = LI()
    for i in range(n):
        a[i] -= 1
    count = defaultdict(lambda : 0)
    l = defaultdict(lambda : 0)
    lis = []
    for i in range(n):
        ai = a[i]
        if count[ai] == 0:
            l[ai] = i
            lis.append(ai)
        count[ai] += 1
    f = defaultdict(lambda : 0)
    r = defaultdict(lambda : 0)
    for i in range(n)[::-1]:
        ai = a[i]
        if not f[ai]:
            r[ai] = i
            f[ai] = 1
    f = [0]*n
    for i in lis:
        li,ri = l[i],r[i]
        f[li] += 1
        f[ri] -= 1
    for i in range(n-1):
        if f[i] > 0:
            x,y = a[i], a[i+1]
            if root(x) != root(y):
                unite(x,y)
        f[i+1] += f[i]
    size = defaultdict(lambda : [])
    for i in l:
        size[root(i)].append(count[i])
    ans = 0
    for i in size.values():
        ans += sum(i)-max(i)
    print(ans)
    return

#H
def H():

    return

#Solve
def __starting_point():
    G()

__starting_point()

MAXN = 200100

n, q = list(map(int, input().split()))
a = list(map(int, input().split()))
lpos = [-1]*MAXN
for i in range(n):
	lpos[a[i]] = i
need = 0
i = 0
while i < n:
	start = i
	r = lpos[a[i]]
	j = i + 1
	while j < r:
		r = max(r, lpos[a[j]])
		j += 1
	cnts = {}
	while i <= r:
		if a[i] in cnts:
			cnts[a[i]] += 1
		else:
			cnts[a[i]] = 1
		i += 1
	best = 0
	for k, v in list(cnts.items()):
		best = max(best, v)
	need += i - start - best

print(need)


MAXN = 200100

n, q = list(map(int, input().split()))
a = list(map(int, input().split()))
lpos = [-1]*MAXN
for i in range(n):
	lpos[a[i]] = i
need = 0
i = 0
while i < n:
	start = i
	r = lpos[a[i]]
	cnts = {}
	while i <= r:
		r = max(r, lpos[a[i]])
		if a[i] in cnts:
			cnts[a[i]] += 1
		else:
			cnts[a[i]] = 1
		i += 1 
	need += i - start - max(cnts.values())

print(need)


from sys import stdin
n,m=list(map(int,stdin.readline().strip().split()))
s=list(map(int,stdin.readline().strip().split()))
mx=200000
arr=[-1 for i in range(mx+1)]
visited=[False for i in range(mx+1)]
cnt=[0 for i in range(mx+1)]
for i in range(n):
    arr[s[i]]=i
x=0
ans=0
inf=mx+30
while x<n:
    ind=arr[s[x]]
    v=[]
    l=x
    while x<=ind and x<n:
        ind=max(arr[s[x]],ind)
        v.append(s[x])
        cnt[s[x]]+=1
        x+=1
    aux=0
    for i in v:
        aux=max(aux,cnt[i])
    ans+=(x-l-aux)
        
    
print(ans)


n, q = map(int, input().split())
a    = list(map(int, input().split()))
d    =  {}

def max_frequent(s, e, a):
    d = {}
    for x in a[s: e+1]:
        if x not in d:
            d[x] = 0
        d[x] += 1
        
    return e - s + 1 - max(list(d.values()))     
    
for i, x in enumerate(a):
    if x not in d:
        d[x] = []
    d[x].append(i)

segment = [[v[0], v[-1]] for v in d.values()]    
end     = -1
start   = -1 
block   = []

for s, e in segment:
    if s > end:
        if end != -1:
            block.append([start, end])
        start = s   
        end   = e 
    if e > end:
        end = e
        
block.append([start, end])        

cnt = 0
for s, e in block:
    cnt += max_frequent(s, e, a)
print(cnt)       

n, _q = map(int, input().split())
mni = [-1] * 200001
mxi = [-1] * 200001
cnt = [0] * 200001
nd = 0
a = list(map(int, input().split()))
for i, v in enumerate(a):
    if mni[v] == -1: mni[v] = i; nd += 1
    mxi[v] = i
    cnt[v] += 1
r = 0
z = 0
currmax = 0
for i, v in enumerate(a):
    if i == mni[v]: z += 1
    if i == mxi[v]: z -= 1
    currmax = max(currmax, cnt[v])
    if z == 0: r += currmax; currmax = 0
print(n - r)

n, q = map(int,input().split())
A = list(map(int,input().split()))
sizes = dict()


for j in range(n):
    if A[j] in sizes:
        sizes[A[j]][2] += 1
        sizes[A[j]][1] = j
    else:
        sizes[A[j]] = [j,j,1]
#print(sizes)

answer = 0
end = -1
max_size = -1
for j in range(n):
    end = max(end, sizes[A[j]][1])
    max_size = max(max_size, sizes[A[j]][2])
    if j == end:
        answer+= max_size
        #print(j, max_size)
        max_size = 0

answer = -answer

for j in sizes:
    answer += sizes[j][2]

print(answer)

import itertools
import sys

def __starting_point():
    n, q = map(int, input().split())
    blocks = list(map(int, input().split()))
    # create empty dictionary - unordered collection
    dif = dict()

    for i in range(n):
        if blocks[i] in dif:
            dif[blocks[i]][1] = i
            dif[blocks[i]][2] = dif[blocks[i]][2] + 1
        elif blocks[i] not in dif:
            dif[blocks[i]] = [i, i, 1]

    rez = 0
    end = -1
    maxi = -1
    for i in range(n):
        if dif[blocks[i]][1] >= end:
            end = dif[blocks[i]][1]
        if dif[blocks[i]][2] >= maxi:
            maxi = dif[blocks[i]][2]
        if i == end:
            rez  = rez + maxi
            maxi = 0
    rez = (-1) * rez
    for i in dif:
        rez = rez + dif[i][2]
    print(rez)
__starting_point()