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: HARD
Tags: Amortized analysis

Implementation

Greedy algorithms

Spanning trees

Data structures
Skill types: Data structures

Amortized analysis

Greedy algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.buffer.readline

def find(x):
	if par[x] == x:
		return x
	par[x] = find(par[x])
	return par[x]

def union(a, b):
	xa = find(a)
	xb = find(b)
	if size[xa] > size[xb]:
		(xa, xb) = (xb, xa)
	par[xa] = xb
	size[xb] += size[xa]
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
par = [i for i in range(max(a) + 1)]
size = [1 for i in range(max(a) + 1)]
counted = [0 for i in range(max(a) + 1)]
for i in range(n):
	counted[a[i]] += 1
first = [0 for i in range(max(a) + 1)]
last = [0 for i in range(max(a) + 1)]
for i in range(n):
	if first[a[i]] == 0:
		first[a[i]] = i
for i in range(n - 1, -1, -1):
	if last[a[i]] == 0:
		last[a[i]] = i
count = 0
spread = 0
counted1 = counted[:]
for i in range(n):
	if count > 0:
		union(a[i], a[i - 1])
	spread = max(spread, last[a[i]])
	counted1[a[i]] -= 1
	if spread == last[a[i]] and counted1[a[i]] == 0:
		count = 0
	else:
		count += 1
maxid = [0 for i in range(max(a) + 1)]
for i in range(1, max(a) + 1):
	par[i] = find(par[i])
for i in range(1, max(a) + 1):
	maxid[par[i]] = max(maxid[par[i]], counted[i])
diff = 0
for i in range(max(a) + 1):
	diff += maxid[i]
print(n - diff)


mod = 10 ** 9 + 7
from sys import stdin, stdout
import bisect
from bisect import bisect_left as bl
from bisect import bisect_right as br
import itertools
import collections
import math
import heapq
from random import randint as rn

def modinv(n, p):
	return pow(n, p - 2, p)

def ncr(n, r, p):
	t = fact[n] * (ifact[r] * ifact[n - r] % p) % p
	return t

def ain():
	return list(map(int, sin().split()))

def sin():
	return input()

def inin():
	return map(int, input().split())

def GCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def main():
	(n, q) = inin()
	a = ain()
	d = {}
	e = {}
	for i in range(n):
		e[a[i]] = i
		if a[i] in d:
			d[a[i]] += 1
		else:
			d[a[i]] = 1
	i = 0
	su = 0
	while i < n:
		x = e[a[i]]
		ans = d[a[i]]
		while i <= x:
			ans = max(ans, d[a[i]])
			x = max(x, e[a[i]])
			i += 1
		su += ans
	print(n - su)
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


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) = 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) = map(int, input().split())
A = list(map(int, input().split()))
if max(A) == min(A):
	print(0)
	sys.exit()
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)


import itertools
import sys
(n, q) = map(int, input().split())
blocks = list(map(int, input().split()))
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)


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=300006, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl = pCrawl.children[index]
		pCrawl.isEndOfWord = True

	def search(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return False
			pCrawl = pCrawl.children[index]
		return pCrawl != None and pCrawl.isEndOfWord

class Node:

	def __init__(self, data):
		self.data = data
		self.count = 0
		self.left = None
		self.right = None

class BinaryTrie:

	def __init__(self):
		self.root = Node(0)

	def insert(self, pre_xor):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = pre_xor & 1 << i
			if val:
				if not self.temp.right:
					self.temp.right = Node(0)
				self.temp = self.temp.right
				self.temp.count += 1
			if not val:
				if not self.temp.left:
					self.temp.left = Node(0)
				self.temp = self.temp.left
				self.temp.count += 1
		self.temp.data = pre_xor

	def query(self, xor):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = xor & 1 << i
			if not val:
				if self.temp.left and self.temp.left.count > 0:
					self.temp = self.temp.left
				elif self.temp.right:
					self.temp = self.temp.right
			elif self.temp.right and self.temp.right.count > 0:
				self.temp = self.temp.right
			elif self.temp.left:
				self.temp = self.temp.left
			self.temp.count -= 1
		return xor ^ self.temp.data
(n, k) = map(int, input().split())
l = list(map(int, input().split()))
la = defaultdict(int)
for i in range(n):
	la[l[i]] = i
i = 0
ans = 0
c = defaultdict(int)
while i < n:
	st = i
	last = la[l[st]]
	ma = 0
	while st <= last:
		c[l[st]] += 1
		last = max(last, la[l[st]])
		st += 1
		ma = max(ma, c[l[st - 1]])
	ans += last - i + 1 - ma
	i = last + 1
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)


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


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)


MAXN = 200100
(n, q) = 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 cnts.items():
		best = max(best, v)
	need += i - start - best
print(need)


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) = 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)


def naiveSolve():
	return
from collections import Counter

def main():
	indexes = [[] for _ in range(200001)]
	(n, q) = readIntArr()
	a = readIntArr()
	for (i, x) in enumerate(a):
		indexes[x].append(i)
	groups = []
	left = 0
	currMaxIdx = 0
	for (i, x) in enumerate(a):
		currMaxIdx = max(currMaxIdx, indexes[x][-1])
		if currMaxIdx == i:
			groups.append((left, i))
			currMaxIdx = i + 1
			left = i + 1
	ans = 0
	for (left, right) in groups:
		cnt = Counter()
		for i in range(left, right + 1):
			cnt[a[i]] += 1
		ans += right - left + 1 - max(cnt.values())
	print(ans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(r):
	print('? {}'.format(r))
	sys.stdout.flush()
	return readIntArr()

def answerInteractive(adj, n):
	print('!')
	for u in range(1, n + 1):
		for v in adj[u]:
			if v > u:
				print('{} {}'.format(u, v))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
from math import gcd, floor, ceil
for _abc in range(1):
	main()


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

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

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

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

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

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

def F():
	return

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

def H():
	return

def __starting_point():
	G()
__starting_point()


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
ii = lambda : int(input())
kk = lambda : map(int, input().split())
ll = lambda : list(kk())
(n, _) = kk()
ls = ll()
(cnt, maxi) = ({}, {})
for (i, l) in enumerate(ls):
	if l not in cnt:
		cnt[l] = 0
	cnt[l] += 1
	maxi[l] = i
nxt = su = 0
while nxt < n:
	l = nxt
	r = maxi[ls[l]]
	maxc = cnt[ls[l]]
	while l < r:
		l += 1
		if maxi[ls[l]] > r:
			r = maxi[ls[l]]
		if cnt[ls[l]] > maxc:
			maxc = cnt[ls[l]]
	su += r - nxt - maxc + 1
	nxt = r + 1
print(su)


(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]
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
		max_size = 0
answer = -answer
for j in sizes:
	answer += sizes[j][2]
print(answer)