One day you wanted to read something, so you went to your bookshelf to grab some book. But when you saw how messy the bookshelf was you decided to clean it up first.

There are $n$ books standing in a row on the shelf, the $i$-th book has color $a_i$.

You'd like to rearrange the books to make the shelf look beautiful. The shelf is considered beautiful if all books of the same color are next to each other.

In one operation you can take one book from any position on the shelf and move it to the right end of the shelf.

What is the minimum number of operations you need to make the shelf beautiful?


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 5 \cdot 10^5$) — the number of books.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — the book colors.


-----Output-----

Output the minimum number of operations to make the shelf beautiful.


-----Examples-----

Input
5
1 2 2 1 3
Output
2
Input
5
1 2 2 1 1
Output
1


-----Note-----

In the first example, we have the bookshelf $[1, 2, 2, 1, 3]$ and can, for example:

take a book on position $4$ and move to the right end: we'll get $[1, 2, 2, 3, 1]$;

take a book on position $1$ and move to the right end: we'll get $[2, 2, 3, 1, 1]$.

In the second example, we can move the first book to the end of the bookshelf and get $[2,2,1,1,1]$.

Source: codeforces | Difficulty: VERY_HARD
Tags: Dynamic programming

Data structures

Greedy algorithms


Solutions:
from collections import Counter
n = int(input())
A = list(map(int, input().split()))
(left, right) = ({}, {})
dp = [0] * (n + 1)
cnt = Counter()
for (i, a) in enumerate(A):
	left.setdefault(a, i)
	right[a] = i
for i in range(n - 1, -1, -1):
	dp[i] = dp[i + 1]
	cnt[A[i]] += 1
	dp[i] = max(dp[i], dp[right[A[i]] + 1] + cnt[A[i]]) if i == left[A[i]] else max(dp[i], cnt[A[i]])
print(n - dp[0])


n = int(input())
A = list(map(int, input().split()))
l = [-1 for i in range(n + 1)]
r = [-1 for i in range(n + 1)]
for i in range(n):
	if l[A[i]] == -1:
		l[A[i]] = i
	r[A[i]] = i
DP = [0 for i in range(n + 1)]
cnt = [0 for i in range(n + 1)]
for i in range(n - 1, -1, -1):
	cnt[A[i]] = cnt[A[i]] + 1
	if l[A[i]] == i:
		DP[i] = cnt[A[i]] + DP[r[A[i]] + 1]
		DP[i] = max(DP[i], DP[i + 1])
	else:
		DP[i] = cnt[A[i]]
		DP[i] = max(DP[i], DP[i + 1])
print(n - DP[0])


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
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')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def A(n):
	return [0] * n

def AI(n, x):
	return [x] * n

def G(n):
	return [[] for i in range(n)]

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	fact(x, mod)
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa.reverse()

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def floorsum(a, b, c, n):
	if a == 0:
		return b // c * (n + 1)
	if a >= c or b >= c:
		return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
	m = (a * n + b) // c
	return n * m - floorsum(c, c - b - 1, a, m - 1)

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

def lowbit(n):
	return n & -n

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class ST:

	def __init__(self, arr):
		n = len(arr)
		mx = n.bit_length()
		self.st = [[0] * mx for i in range(n)]
		for i in range(n):
			self.st[i][0] = arr[i]
		for j in range(1, mx):
			for i in range(n - (1 << j) + 1):
				self.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])

	def query(self, l, r):
		if l > r:
			return -inf
		s = (r + 1 - l).bit_length() - 1
		return max(self.st[l][s], self.st[r - (1 << s) + 1][s])

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return flag

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		seen.add(u)
		for (v, w) in graph[u]:
			if v not in d or d[v] > d[u] + w:
				d[v] = d[u] + w
				heappush(heap, (d[v], v))
	return d

def lcm(a, b):
	return a * b // gcd(a, b)

def lis(nums):
	res = []
	for k in nums:
		i = bisect.bisect_left(res, k)
		if i == len(res):
			res.append(k)
		else:
			res[i] = k
	return len(res)

def RP(nums):
	n = len(nums)
	s = set(nums)
	d = {}
	for (i, k) in enumerate(sorted(s), 1):
		d[k] = i
	bi = BIT([0] * (len(s) + 1))
	ans = 0
	for i in range(n - 1, -1, -1):
		ans += bi.query(d[nums[i]] - 1)
		bi.update(d[nums[i]], 1)
	return ans

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j, n, m):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

def topo(n):
	q = deque()
	res = []
	for i in range(1, n + 1):
		if ind[i] == 0:
			q.append(i)
			res.append(i)
	while q:
		u = q.popleft()
		for v in g[u]:
			ind[v] -= 1
			if ind[v] == 0:
				q.append(v)
				res.append(v)
	return res

@bootstrap
def gdfs(r, p):
	if len(g[r]) == 1 and p != -1:
		yield None
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None
t = 1
for i in range(t):
	n = N()
	a = RLL()
	l = AI(n + 1, n)
	r = AI(n + 1, 0)
	for i in range(n):
		l[a[i]] = min(i, l[a[i]])
		r[a[i]] = max(i, r[a[i]])
	dp = A(n + 1)
	c = A(n + 1)
	for i in range(n - 1, -1, -1):
		c[a[i]] += 1
		dp[i] = max(dp[i + 1], c[a[i]])
		if i == l[a[i]]:
			dp[i] = max(dp[i], c[a[i]] + dp[r[a[i]] + 1])
	ans = n - max(dp)
	print(ans)


n = int(input())
a = [int(t) - 1 for t in input().split()]
(l, r) = ([-1] * n, [-1] * n)
for (i, x) in enumerate(a):
	if l[x] == -1:
		l[x] = i
	r[x] = i
dp = [0] * (n + 1)
cnt = [0] * n
for i in reversed(range(n)):
	x = a[i]
	cnt[x] += 1
	dp[i] = dp[i + 1]
	if i == l[x]:
		dp[i] = max(dp[i], dp[r[x] + 1] + cnt[x])
	else:
		dp[i] = max(dp[i], cnt[x])
print(n - dp[0])


from collections import defaultdict
n = int(input())
lst = list(map(int, input().split(' ')))
arr = [[-1 for i in range(2)] for j in range(n + 1)]
for i in range(n):
	if arr[lst[i]][0] == -1:
		arr[lst[i]][0] = i
		arr[lst[i]][1] = i
	arr[lst[i]][1] = i
a = defaultdict(lambda : 0)
dp = [0] * (n + 1)
for i in range(n - 1, -1, -1):
	a[lst[i]] += 1
	if i == arr[lst[i]][0]:
		dp[i] = max(dp[i + 1], a[lst[i]] + dp[arr[lst[i]][1] + 1])
	else:
		dp[i] = max(dp[i + 1], a[lst[i]])
print(n - dp[0])


import sys, getpass
import math, random
import functools, itertools, collections, heapq, bisect
from collections import Counter, defaultdict, deque
input = sys.stdin.readline
M9 = 10 ** 9 + 7
MAXINT = sys.maxsize
OFFLINE_TEST = getpass.getuser() == 'hkmac'

def log(*args):
	if OFFLINE_TEST:
		print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)

def solve(*args):
	if OFFLINE_TEST:
		log('----- solving ------')
		log(*args)
		log('----- ------- ------')
	return solve_(*args)

def read_matrix(rows):
	return [list(map(int, input().split())) for _ in range(rows)]

def read_strings(rows):
	return [input().strip() for _ in range(rows)]

def solve_(lst):
	left = {}
	right = {}
	c = Counter(lst)
	for (i, x) in enumerate(lst):
		if x not in left:
			left[x] = i
		right[x] = i
	c2 = Counter()
	dp = [0 for _ in range(len(lst) + 1)]
	for (i, x) in reversed(list(enumerate(lst))):
		c2[x] += 1
		if left[x] == i:
			dp[i] = c[x] + dp[right[x] + 1]
		else:
			dp[i] = c2[x]
		dp[i] = max(dp[i], dp[i + 1])
	log(dp)
	return len(lst) - dp[0]
for case_num in [0]:
	k = int(input())
	lst = list(map(int, input().split()))
	res = solve(lst)
	print(res)


n = int(input())
a = [int(x) - 1 for x in input().split()]
l = [-1 for _ in range(n + 1)]
r = [-1 for _ in range(n + 1)]
freq = [0 for _ in range(n + 1)]
dp = [0 for _ in range(n + 1)]
for i in range(n):
	if l[a[i]] == -1:
		l[a[i]] = i
	r[a[i]] = i
for i in range(n - 1, -1, -1):
	dp[i] = dp[i + 1]
	freq[a[i]] += 1
	if i == l[a[i]]:
		dp[i] = max(dp[i], dp[r[a[i]] + 1] + freq[a[i]])
	else:
		dp[i] = max(dp[i], freq[a[i]])
print(n - dp[0])


from collections import defaultdict, Counter

def get():
	n = int(input())
	nums = list(map(int, input().split()))
	return (n, nums)

def sort_book():
	(n, nums) = get()
	(min_idx, max_idx) = (dict(), dict())
	val_to_idx = defaultdict(list)
	counter = Counter()
	for (i, x) in enumerate(nums):
		if x not in min_idx:
			min_idx[x] = i
			max_idx[x] = i
		min_idx[x] = min(i, min_idx[x])
		max_idx[x] = max(i, max_idx[x])
		val_to_idx[x].append(i)
	dp = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		x = nums[i]
		counter[x] += 1
		dp[i] = dp[i + 1]
		if i == min_idx[x]:
			dp[i] = max(dp[i], len(val_to_idx[x]) + dp[max_idx[x] + 1])
		else:
			dp[i] = max(dp[i], counter[x])
	return n - dp[0]
print(sort_book())


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def MI():
	return map(int, sys.stdin.buffer.readline().split())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LI1():
	return list(map(int1, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()
inf = 10 ** 16
md = 10 ** 9 + 7
n = II()
aa = LI1()
ll = [-1] * n
rr = [-1] * n
cnt = [0] * n
cs = [0] * (n + 1)
for i in range(n - 1, -1, -1):
	a = aa[i]
	if rr[a] == -1:
		rr[a] = i
	ll[a] = i
	cnt[a] += 1
	cs[i] = cnt[a]

def chmax(i, val):
	if val > dp[i]:
		dp[i] = val
dp = [-1] * (n + 1)
dp[n] = 0
for i in range(n - 1, -1, -1):
	a = aa[i]
	dp[i] = dp[i + 1]
	if ll[a] == i:
		chmax(i, dp[rr[a] + 1] + cs[i])
	else:
		chmax(i, cs[i])
print(n - dp[0])


import sys
import math
from itertools import permutations

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()

def FACT(n, mod):
	s = 1
	facts = [1]
	for i in range(1, n + 1):
		s *= i
		s %= mod
		facts.append(s)
	return facts[n]

def C(n, k, mod):
	return FACT(n, mod) * pow(FACT(k, mod) * FACT(n - k, mod) % mod, mod - 2, mod) % mod
n = II()
a = LI()
d = [[-1, -1] for i in range(n + 1)]
count = [0 for i in range(n + 1)]
for i in range(n):
	temp = d[a[i]]
	count[a[i]] += 1
	if temp[0] == -1:
		temp[0] = i
	temp[1] = i
dp = [0 for i in range(n + 1)]
cf = [0 for i in range(n + 1)]
for i in range(n - 1, -1, -1):
	dp[i] = dp[i + 1]
	cf[a[i]] += 1
	if i == d[a[i]][0]:
		dp[i] = max(dp[i], dp[d[a[i]][1] + 1] + count[a[i]])
	else:
		dp[i] = max(dp[i], cf[a[i]])
print(n - dp[0])


from collections import defaultdict
from itertools import accumulate
import sys
input = sys.stdin.readline
inf = 100000000000000000
mod = 998244353
n = int(input())
A = list(map(int, input().split()))
l = [-1] * (n + 1)
r = [-1] * (n + 1)
F = [0] * (n + 1)
cnt = [0] * (n + 1)
for (num, a) in enumerate(A):
	if l[a] == -1:
		l[a] = num
	r[a] = num
for i in range(n - 1, -1, -1):
	F[i] = F[i + 1]
	nowcol = A[i]
	cnt[nowcol] += 1
	if i == l[nowcol]:
		F[i] = max(F[i], F[r[nowcol] + 1] + cnt[nowcol])
	else:
		F[i] = max(F[i], cnt[nowcol])
print(n - F[0])


n = int(input())
a = [int(i) for i in input().split()]
left = {}
right = {}
freq = {}
freq_so_far = []
for (i, color) in enumerate(a):
	if color not in left:
		left[color] = i
		freq[color] = 0
	right[color] = i
	freq[color] += 1
	freq_so_far.append(freq[color])
dp = [n] * (n + 1)
dp[-1] = 0
for i in range(n - 1, -1, -1):
	color = a[i]
	if left[color] == i:
		best_unmoved = freq[color] + dp[right[color] + 1]
	else:
		best_unmoved = freq[color] - freq_so_far[i] + 1
	dp[i] = max(dp[i + 1], best_unmoved)
print(n - dp[0])


from collections import defaultdict, Counter
from sys import stdin
input = stdin.readline
n = int(input())
a = list(map(int, input().split()))
fq = Counter()
fl = defaultdict(lambda : [n + 1, -1])
for (i, el) in enumerate(a):
	fl[el][0] = min(fl[el][0], i)
	fl[el][1] = i
	fq[el] += 1
cnt = Counter()
dp = [0] * (n + 1)
for i in range(n - 1, -1, -1):
	el = a[i]
	cnt[el] += 1
	dp[i] = dp[i + 1]
	if i == fl[el][0]:
		dp[i] = max(dp[i], dp[fl[el][1] + 1] + fq[el])
	else:
		dp[i] = max(dp[i], cnt[el])
print(max(n - dp[0], 0))


from collections import *
n = int(input())
nums = list(map(int, input().split()))
counters = Counter()
dict = defaultdict(lambda : [n + 1, -1])
for (i, count) in enumerate(nums):
	dict[count][0] = min(dict[count][0], i)
	dict[count][1] = i
	counters[count] += 1
counters2 = Counter()
memo = [0] * (n + 1)
for j in range(len(nums) - 1, -1, -1):
	elem = nums[j]
	counters2[elem] += 1
	memo[j] = memo[j + 1]
	if j == dict[elem][0]:
		memo[j] = max(memo[j], memo[dict[elem][1] + 1] + counters[elem])
	else:
		memo[j] = max(memo[j], counters2[elem])
print(max(n - memo[0], 0))


def solve(n, cols):
	right = {}
	left = {}
	cnt = {}
	for i in range(n):
		if cols[i] not in left:
			left[cols[i]] = i
			cnt[cols[i]] = 0
		right[cols[i]] = i
	dp = [0] * (n + 1)
	for i in reversed(range(n)):
		cnt[cols[i]] += 1
		if i == left[cols[i]]:
			dp[i] = max(dp[i + 1], cnt[cols[i]] + dp[right[cols[i]] + 1])
		else:
			dp[i] = max(dp[i + 1], cnt[cols[i]])
	return n - dp[0]
n = int(input().strip())
cols = [int(x) for x in input().strip().split()]
print(solve(n, cols))


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

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def S():
	return input().strip()

def print_list(l):
	print(' '.join(map(str, l)))
from collections import defaultdict as dc
n = N()
a = RLL()
count = [0] * (n + 1)
first = {}
last = {}
for i in range(n):
	if a[i] not in first:
		first[a[i]] = i
	last[a[i]] = i
dp = [0] * (n + 1)
for i in range(n - 1, -1, -1):
	count[a[i]] += 1
	tail = dp[last[a[i]] + 1] if i == first[a[i]] else 0
	dp[i] = max(dp[i + 1], count[a[i]] + tail)
print(n - dp[0])


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
import time
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		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 = self.os.read(self._fd, max(self.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 = self.os.read(self._fd, max(self.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:
			self.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')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def isInt(s):
	return '0' <= s[0] <= '9'
MOD = 10 ** 9 + 7

def solve():
	N = getInt()
	A = getInts()
	(left, right, counts, tmp_counts) = ([-1] * (N + 1), [-1] * (N + 1), [0] * (N + 1), [0] * (N + 1))
	for i in range(N - 1, -1, -1):
		left[A[i]] = i
		counts[A[i]] += 1
		if counts[A[i]] == 1:
			right[A[i]] = i
	dp = [-1] * (N + 1)
	dp[N] = 0
	for i in range(N - 1, -1, -1):
		dp[i] = dp[i + 1]
		tmp_counts[A[i]] += 1
		if i == left[A[i]]:
			dp[i] = max(dp[i], dp[right[A[i]] + 1] + counts[A[i]])
		else:
			dp[i] = max(dp[i], tmp_counts[A[i]])
	return N - dp[0]
print(solve())


n = int(input())
a = [int(x) - 1 for x in input().split()]
cnt = [0 for i in range(n)]
l = [-1 for i in range(n)]
r = [-1 for i in range(n)]
for i in range(n):
	cnt[a[i]] += 1
	if l[a[i]] == -1:
		l[a[i]] = i
	r[a[i]] = i
dp = [10 ** 9 for i in range(n + 1)]
ans = n
dp[0] = 0
for i in range(n):
	dp[i + 1] = min(dp[i + 1], dp[i] + 1)
	if l[a[i]] == i:
		dp[r[a[i]] + 1] = min(dp[r[a[i]] + 1], dp[i] + r[a[i]] - i + 1 - cnt[a[i]])
	ans = min(ans, dp[i] + n - i - cnt[a[i]])
	cnt[a[i]] -= 1
print(min(ans, dp[n]))


import sys
input = lambda : sys.stdin.readline().rstrip()
n = int(input())
a = list(map(int, input().split()))
a = [a[i] - 1 for i in range(n)]
R = [-1 for i in range(n)]
C = [[] for i in range(n)]
for i in range(n):
	R[a[i]] = i
	C[a[i]].append(i)
backet = [-1 for i in range(n)]
for i in range(n):
	if R[i] != -1:
		backet[R[i]] = i
update = [b for b in backet if b != -1]
dp = [0 for i in range(n)]
res = n
for _ in range(len(update)):
	c = update[_]
	cn = len(C[c])
	for i in range(cn):
		tmp = dp[C[c][i]] + cn - i
		res = min(res, n - tmp)
	start = C[c][0]
	dp[R[c]] = max(dp[R[c]], dp[start] + cn)
	if _ + 1 < len(update):
		nc = update[_ + 1]
		for i in range(R[c], R[nc] + 1):
			dp[i] = dp[R[c]]
print(res)


class Stuct:

	def __init__(self):
		self.leftmost = 0
		self.rightmost = 0
		self.frequency = 0

def get_data(books):
	C = {}
	for (i, b) in enumerate(books):
		if not b in C:
			C[b] = Stuct()
		C[b].frequency += 1
		C[b].rightmost = i
	for (i, b) in reversed(tuple(enumerate(books))):
		C[b].leftmost = i
	return C

def solve(books):
	data = get_data(books)
	Cf = {}
	DP = [0 for _ in range(len(books) + 1)]
	for (i, ai) in reversed(tuple(enumerate(books))):
		if ai not in Cf:
			Cf[ai] = 0
		Cf[ai] += 1
		DP[i] = DP[i + 1]
		if i == data[ai].leftmost:
			DP[i] = max(DP[i], data[ai].frequency + DP[data[ai].rightmost + 1])
		else:
			DP[i] = max(DP[i], Cf[ai])
	return len(books) - DP[0]
N = int(input())
books = tuple(map(int, input().split(' ')))
print(solve(books))


import bisect
n = int(input())
arr = list(map(int, input().split()))
dp = [-1] * n + [0]
rear = n - 1
indexlist = [[] for i in range(n + 1)]
for i in range(n):
	indexlist[arr[i]].append(i)

def getnext(index):
	if index >= rear:
		return 0
	if dp[index] >= 0:
		return dp[index]
	if index == indexlist[arr[index]][0]:
		end = indexlist[arr[index]][-1]
		num1 = end - index + 1 - len(indexlist[arr[index]]) + getnext(end + 1)
	else:
		loc = bisect.bisect_left(indexlist[arr[index]], index)
		num1 = n - index - len(indexlist[arr[index]]) + loc
	num2 = 1 + getnext(index + 1)
	dp[index] = min(num1, num2)
	return min(num1, num2)
for index in range(n - 1, -1, -1):
	if index == indexlist[arr[index]][0]:
		end = indexlist[arr[index]][-1]
		num1 = end - index + 1 - len(indexlist[arr[index]]) + dp[end + 1]
	else:
		loc = bisect.bisect_left(indexlist[arr[index]], index)
		num1 = n - index - len(indexlist[arr[index]]) + loc
	num2 = 1 + dp[index + 1]
	dp[index] = min(num1, num2)
print(dp[0])


def solve(n, arr):
	l = {}
	r = {}
	cnt = {}
	dp = [0] * (n + 1)
	for i in range(n):
		c = arr[i]
		if c not in l:
			l[c] = i
	for i in range(n - 1, -1, -1):
		c = arr[i]
		if c not in cnt:
			r[c] = i
			cnt[c] = 0
		cnt[c] += 1
		dp[i] = dp[i + 1]
		if l[c] == i:
			dp[i] = max(dp[i], cnt[c] + dp[r[c] + 1])
		else:
			dp[i] = max(dp[i], cnt[c])
	return n - dp[0]
n = int(input())
arr = list(map(int, input().split()))
print(solve(n, arr))


import sys
from sys import stdin
n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
clis = [[] for i in range(n + 1)]
for i in range(n):
	clis[a[i]].append(i)
dp = [0] * (n + 1)
app = [0] * (n + 1)
for i in range(n - 1, -1, -1):
	app[a[i]] += 1
	dp[i] = max(dp[i], dp[i + 1], app[a[i]])
	if clis[a[i]][0] == i:
		dp[i] = max(dp[i], dp[clis[a[i]][-1] + 1] + len(clis[a[i]]))
print(n - dp[0])


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
a = [int(x) - 1 for x in input().split()]
l = [-1 for _ in range(n + 1)]
r = [-1 for _ in range(n + 1)]
freq = [0 for _ in range(n + 1)]
dp = [0 for _ in range(n + 1)]
for i in range(n):
	if l[a[i]] == -1:
		l[a[i]] = i
	r[a[i]] = i
for i in range(n - 1, -1, -1):
	dp[i] = dp[i + 1]
	freq[a[i]] += 1
	if i == l[a[i]]:
		dp[i] = max(dp[i], dp[r[a[i]] + 1] + freq[a[i]])
	else:
		dp[i] = max(dp[i], freq[a[i]])
print(n - dp[0])