The only difference between the two versions is that this version asks the minimal possible answer.

Homer likes arrays a lot. Today he is painting an array $a_1, a_2, \dots, a_n$ with two kinds of colors, white and black. A painting assignment for $a_1, a_2, \dots, a_n$ is described by an array $b_1, b_2, \dots, b_n$ that $b_i$ indicates the color of $a_i$ ($0$ for white and $1$ for black).

According to a painting assignment $b_1, b_2, \dots, b_n$, the array $a$ is split into two new arrays $a^{(0)}$ and $a^{(1)}$, where $a^{(0)}$ is the sub-sequence of all white elements in $a$ and $a^{(1)}$ is the sub-sequence of all black elements in $a$. For example, if $a = [1,2,3,4,5,6]$ and $b = [0,1,0,1,0,0]$, then $a^{(0)} = [1,3,5,6]$ and $a^{(1)} = [2,4]$.

The number of segments in an array $c_1, c_2, \dots, c_k$, denoted $\mathit{seg}(c)$, is the number of elements if we merge all adjacent elements with the same value in $c$. For example, the number of segments in $[1,1,2,2,3,3,3,2]$ is $4$, because the array will become $[1,2,3,2]$ after merging adjacent elements with the same value. Especially, the number of segments in an empty array is $0$.

Homer wants to find a painting assignment $b$, according to which the number of segments in both $a^{(0)}$ and $a^{(1)}$, i.e. $\mathit{seg}(a^{(0)})+\mathit{seg}(a^{(1)})$, is as small as possible. Find this number.


-----Input-----

The first line contains an integer $n$ ($1 \leq n \leq 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq n$).


-----Output-----

Output a single integer, indicating the minimal possible total number of segments.


-----Examples-----

Input
6
1 2 3 1 2 2
Output
4
Input
7
1 2 1 2 1 2 1
Output
2


-----Note-----

In the first example, we can choose $a^{(0)} = [1,1,2,2]$, $a^{(1)} = [2,3]$ and $\mathit{seg}(a^{(0)}) = \mathit{seg}(a^{(1)}) = 2$. So the answer is $2+2 = 4$.

In the second example, we can choose $a^{(0)} = [1,1,1,1]$, $a^{(1)} = [2,2,2]$ and $\mathit{seg}(a^{(0)}) = \mathit{seg}(a^{(1)}) = 1$. So the answer is $1+1 = 2$.

Difficulty: HARD
Tags: Constructive algorithms

Implementation

Greedy algorithms

Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures

Greedy algorithms

Starter code:

Solutions:
from collections import defaultdict
n = int(input())
l = list(map(int, input().split()))
d = defaultdict(list)
a = 0
b = 0
cnt = 0
for i in range(n + 1):
	d[i].append(10 ** 5 + 1)
for i in range(n - 1, -1, -1):
	d[l[i]].append(i)
for i in range(n):
	d[l[i]].pop()
	if l[i] != a and l[i] != b:
		if d[a][-1] > d[b][-1]:
			a = l[i]
		else:
			b = l[i]
		cnt += 1
print(cnt)


import sys
input = lambda : sys.stdin.readline().rstrip()
N = int(input())
A = [int(a) for a in input().split()]
S = set()
ans = 0
la = -1
for a in A:
	if a == la:
		continue
	elif a in S:
		S = {a, la}
	else:
		S.add(a)
		la = a
		ans += 1
print(ans)


import sys
input = sys.stdin.readline
import bisect
n = int(input())
A = list(map(int, input().split()))
B = [-1]
for a in A:
	if a == B[-1]:
		continue
	else:
		B.append(a)
B = B[1:]
LEN = len(B)
X = [[] for i in range(n + 1)]
for i in range(LEN):
	X[B[i]].append(i)
DP = [1 << 30] * LEN
DP[0] = 1
for i in range(LEN):
	DP[i] = min(DP[i - 1] + 1, DP[i])
	k1 = B[i]
	x = bisect.bisect(X[k1], i)
	if x == len(X[k1]):
		True
	elif i - 1 >= 0 and B[i - 1] == B[i + 1]:
		DP[X[k1][x]] = min(DP[X[k1][x]], DP[i] + X[k1][x] - X[k1][x - 1] - 2)
	else:
		DP[X[k1][x]] = min(DP[X[k1][x]], DP[i] + X[k1][x] - X[k1][x - 1] - 1)
	if i - 1 >= 0:
		k2 = B[i - 1]
		x = bisect.bisect(X[k2], i - 1)
		if x == len(X[k2]):
			True
		else:
			DP[X[k2][x]] = min(DP[X[k2][x]], DP[i] + X[k2][x] - X[k2][x - 1] - 2)
print(DP[-1])


import os, sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	arr = list(map(int, input().split()))
	a = [arr[0]]
	for i in range(1, n):
		if a[-1] != arr[i]:
			a.append(arr[i])
	(n1, n) = (n, len(a))
	if n == 1:
		print(1)
		return
	ne = [n + 1] * n
	dct = [-1 for _ in range(n1 + 1)]
	for (ind, i) in enumerate(a):
		if dct[i] == -1:
			dct[i] = ind
		else:
			ne[dct[i]] = ind
			dct[i] = ind
	(x, y, ans) = (0, 1, 2)
	for i in range(2, n):
		if a[x] == a[i]:
			x = i
		elif a[y] == a[i]:
			y = i
		elif ne[x] < ne[y]:
			y = i
			ans += 1
		else:
			x = i
			ans += 1
	print(ans)
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')
main()


from sys import stdin, stdout
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
n = int(inp())
count = [[] for i in range(n + 1)]
arr = lmp()
for i in range(n):
	count[arr[i]].append(i)
for i in range(n + 1):
	count[i].reverse()
a = [arr[0]]
b = [0]
count[arr[0]].pop()
for i in range(1, n):
	if arr[i] == a[-1] or arr[i] == b[-1]:
		pass
	else:
		xa = inf if len(count[a[-1]]) == 0 else count[a[-1]][-1]
		xb = inf if len(count[b[-1]]) == 0 else count[b[-1]][-1]
		if xa == inf:
			a.append(arr[i])
		elif xb == inf:
			b.append(arr[i])
		elif xa < xb:
			b.append(arr[i])
		else:
			a.append(arr[i])
	count[arr[i]].pop()
print(len(a) + len(b) - 1)


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)))
n = N()
a = RLL()
a1 = 0
a2 = 0
s = set()
ans = 0
for i in range(n):
	if a[i] == a1:
		continue
	if a[i] == a2:
		s = {a1}
		continue
	if a[i] in s:
		(a1, a2) = (a[i], a1)
		s = {a1}
	else:
		s.add(a[i])
		a1 = a[i]
		ans += 1
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
if len(set(A)) == 1:
	print(1)
	sys.exit()
B = [A[0]]
for i in range(1, n):
	if A[i] != A[i - 1]:
		B.append(A[i])
D = [B[0], B[1]]
E = [0] * (n + 10)
E[B[0]] = 1
E[B[1]] = 1
top = [B[0], B[1]]
ans0 = 2
tf = 1
for i in range(2, len(B)):
	if B[i] in top and tf == 1:
		continue
	else:
		tf = 0
		if E[B[i]] == 1:
			top = [B[i]]
			for j in range(len(D)):
				E[D[j]] = 0
			for j in range(len(D) - 1, -1, -1):
				if D[j] != B[i]:
					top.append(D[j])
					break
			E[top[0]] = 1
			E[top[1]] = 1
			D = top[:]
			tf = 1
		else:
			E[B[i]] = 1
			D.append(B[i])
			ans0 += 1
print(ans0)


import sys
n = int(input())
a = [0] + [int(x) for x in input().split()]
x = y = 0
p = [n + 1 for x in range(n + 1)]
nxt = [0] * (n + 1)
for i in range(n, -1, -1):
	nxt[i] = p[a[i]]
	p[a[i]] = i
ans = 0
for i in range(1, n + 1):
	if a[x] == a[i] and a[y] == a[i]:
		y = i
	elif a[x] != a[i] and a[y] == a[i]:
		y = i
	elif a[x] == a[i] and a[y] != a[i]:
		x = i
	else:
		if nxt[x] < nxt[y]:
			y = i
		else:
			x = i
		ans += 1
print(ans)


import collections

def solveTestCase():
	n = int(input())
	A = [int(i) for i in input().split()]
	s1 = [0]
	s2 = [0]
	d = dict()
	v = n
	B = []
	for i in A[::-1]:
		nxt = n + 1
		if i in d:
			nxt = d[i]
		B.append((i, nxt))
		d[i] = v
		v -= 1
	B = B[::-1]
	next1 = n + 2
	next2 = n + 2
	for (v, nxt) in B:
		if v == s1[-1]:
			next1 = nxt
		elif v == s2[-1]:
			next2 = nxt
		elif s1[-1] == s2[-1]:
			s1.append(v)
			next1 = nxt
		elif next1 < next2:
			s2.append(v)
			next2 = nxt
		else:
			s1.append(v)
			next1 = nxt
	print(len(s1) + len(s2) - 2)
solveTestCase()


from array import array
from collections import defaultdict

def solve(n, D):
	dict_idx = defaultdict(list)
	for (i, d) in enumerate(D):
		dict_idx[d].append(i)
	dict_count = {}
	for d in dict_idx.keys():
		dict_idx[d].pop(0)
		dict_count[d] = len(dict_idx[d])
	a = None
	b = None
	a_cnt = 0
	b_cnt = 0
	a_next_idx = 10 ** 6
	b_next_idx = 10 ** 6
	for (i, d) in enumerate(D):
		if dict_count[d] > 0:
			next_idx = dict_idx[d].pop(0)
			dict_count[d] -= 1
		else:
			next_idx = 10 ** 6
		if a == d:
			a_next_idx = next_idx
			continue
		if b == d:
			b_next_idx = next_idx
			continue
		if a is None:
			a = d
			a_cnt += 1
			a_next_idx = next_idx
			continue
		if b is None:
			b = d
			b_cnt += 1
			b_next_idx = next_idx
			continue
		if a_next_idx > b_next_idx:
			a = d
			a_cnt += 1
			a_next_idx = next_idx
			continue
		else:
			b = d
			b_cnt += 1
			b_next_idx = next_idx
			continue
	return a_cnt + b_cnt

def main():
	ans = []
	n = int(input())
	D = array('i', list(map(int, input().split(' '))))
	ans.append(solve(n, D))
	for a in ans:
		print(a)
main()


import sys
from collections import defaultdict

def main():
	n = int(sys.stdin.readline())
	a = sys.stdin.readline().split()
	data = []
	prev = {}
	result = 0
	current = [{'val': -1, 'prev': -1}, {'val': -1, 'prev': -1}]
	for (key, val) in enumerate(a):
		data.append({'val': val, 'prev': prev[val] if val in prev else -1})
		prev[val] = key
	for el in reversed(data):
		if el['val'] == current[0]['val']:
			current[0] = el
			continue
		if el['val'] == current[1]['val']:
			current[1] = el
			continue
		result += 1
		if current[0]['prev'] < current[1]['prev']:
			current[0] = el
		else:
			current[1] = el
	print(result)
	return
main()


import sys
readline = sys.stdin.readline
N = int(readline())
A = list(map(int, readline().split()))
INF = 10 ** 9 + 7
res = []
for a in A:
	if not res or res[-1] != a:
		res.append(a)
cnt = 0
res.append(-1)
dp = [INF] * (N + 3)
dp[-1] = 0
geta = 0
mini = 0
for i in range(len(res) - 1):
	cp = res[i - 1]
	cn = res[i]
	dcp = min(mini + geta + 1, dp[cn] + geta)
	geta += 1
	dp[cp] = dcp - geta
	mini = min(mini, dp[cp])
print(min(dp) + geta)


n = int(input())
a1 = list(map(int, input().split()))
sto1 = [[int(100000.0 + 5)] for i in range(n + 1)]
for i in range(n - 1, -1, -1):
	sto1[a1[i]].append(i)
(tmp1, tmp2, ans1) = (0, 0, 0)
for i in range(n):
	if a1[i] == tmp1:
		sto1[a1[i]].pop()
	elif a1[i] == tmp2:
		sto1[a1[i]].pop()
	elif sto1[tmp1][-1] < sto1[tmp2][-1]:
		tmp2 = a1[i]
		ans1 += 1
		sto1[a1[i]].pop()
	else:
		tmp1 = a1[i]
		ans1 += 1
		sto1[a1[i]].pop()
print(ans1)


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')
from collections import Counter, defaultdict
import math
for _ in range(1):
	n = int(input())
	arr = list(map(int, input().split()))
	ind = [[] for i in range(n + 1)]
	for i in range(n):
		ind[arr[i]].append(i)
	ans = 1
	l1 = arr[0]
	l2 = 0
	ind[arr[0]].pop(0)
	for i in range(1, n):
		ind[arr[i]].pop(0)
		if arr[i] == l1:
			pass
		elif arr[i] == l2 or l2 == 0:
			if l2 == 0:
				ans += 1
			l2 = arr[i]
			pass
		else:
			ans += 1
			v1 = 10 ** 10
			v2 = 10 ** 10
			if len(ind[l1]) > 0:
				v1 = ind[l1][0]
			if len(ind[l2]) > 0:
				v2 = ind[l2][0]
			if v1 <= v2:
				l2 = arr[i]
			else:
				l1 = arr[i]
	print(ans)


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 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()
aa0 = LI()
aa = []
for a in aa0:
	if not aa or a != aa[-1]:
		aa.append(a)
if len(aa) == 1:
	print(1)
	exit()
last = [inf] * (n + 1)
n = len(aa)
nxt = [inf] * n
for i in range(n - 1, -1, -1):
	nxt[i] = last[aa[i]]
	last[aa[i]] = i
xx = [aa[0]]
yy = [aa[1]]
(i, j) = (0, 1)
for (k, a) in enumerate(aa):
	if a == xx[-1]:
		i = k
	elif a == yy[-1]:
		j = k
	elif nxt[i] > nxt[j]:
		xx.append(a)
		i = k
	else:
		yy.append(a)
		j = k
print(len(xx) + len(yy))


import sys
input = lambda : sys.stdin.buffer.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())

class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

	def __getitem__(self, k):
		k += self.num
		return self.tree[k]
import random
n = int(input())
a = list(mi())
if n == 1:
	exit(print(1))
a = [a[i] - 1 for i in range(n)]
val = a[0]
new = []
for i in range(1, n):
	if a[i] != val:
		new.append(val)
		val = a[i]
new.append(val)
a = new
dp = SegmentTree([-10 ** 15] * n, max, 0)
n = len(a)
dp.update(a[0], 0)
dp.update(a[1], 0)
for i in range(2, n):
	tmp_same = dp[a[i]] + 1
	tmp_diff = max(dp.query(0, i), dp.query(i + 1, n))
	dp.update(a[i - 1], max(tmp_same, tmp_diff))
print(n - dp.query(0, n))


import sys
Z = sys.stdin.readline
n = int(Z())
a = [*map(int, Z().split())]
b = []
p = 0
for i in a:
	if i != p:
		b.append(i)
		p = i
c = 0
e = [0] * n
r = [0, 0]
lb = len(b)
for i in range(lb):
	if e[-b[i]] == c + 1:
		c += 1
		r = [b[i], b[i - 1]]
		e[-r[0]] = c + 1
		e[-r[1]] = c + 1
	else:
		e[-b[i]] = c + 1
print(lb - c)


from sys import stdin
input = stdin.readline

def main():
	n = int(input())
	ara = [int(x) for x in input().split()]
	positions = [[] for i in range(n + 1)]
	for idx in range(n):
		positions[ara[idx]].append(idx)
	next_ara = [n] * (n + 1)
	for idx in range(n + 1):
		size = len(positions[idx])
		for jdx in range(size):
			if jdx < size - 1:
				next_ara[positions[idx][jdx]] = positions[idx][jdx + 1]
			else:
				next_ara[positions[idx][jdx]] = n
	ara.append(n + n)
	ones = [n]
	zeros = [n]
	ans = 0
	for idx in range(n):
		if ara[idx] == ara[ones[-1]] and ara[idx] == ara[zeros[-1]]:
			ones.append(idx)
		elif ara[idx] == ara[ones[-1]]:
			ones.append(idx)
		elif ara[idx] == ara[zeros[-1]]:
			zeros.append(idx)
		elif next_ara[ones[-1]] > next_ara[zeros[-1]]:
			ones.append(idx)
			ans += 1
		else:
			zeros.append(idx)
			ans += 1
	print(ans)
main()


def main():
	n = int(input())
	a = readIntArr()
	indexes = [[] for _ in range(n + 1)]
	for (i, x) in enumerate(a):
		indexes[x].append(i)
	for x in range(1, n + 1):
		indexes[x].append(inf)

	def getNextIndex(currIndex, x):
		temp = indexes[x]
		n = len(temp)
		i = -1
		b = n
		while b > 0:
			while i + b < n and temp[i + b] <= currIndex:
				i += b
			b //= 2
		i += 1
		return temp[i]
	a0 = -1
	a1 = -1
	ans = 0
	for (i, x) in enumerate(a):
		if x != a0 and x != a1 and (a0 != a1):
			if getNextIndex(i, a0) > getNextIndex(i, a1):
				a0 = x
			else:
				a1 = x
			ans += 1
		elif a0 == a1:
			if a0 != x:
				ans += 1
			a0 = x
		else:
			pass
	print(ans)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

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()]
inf = float('inf')
MOD = 10 ** 9 + 7
main()


from sys import stdin, stdout
from collections import defaultdict
import math

def main():
	n = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	p = [arr[0]]
	for i in range(1, n):
		if arr[i] == p[-1]:
			continue
		p.append(arr[i])
	next_pos = defaultdict(list)
	for i in range(len(p) - 1, -1, -1):
		next_pos[p[i]].append(i)
	a = 0
	b = 0
	mn = 0
	for x in p:
		if x == a or x == b:
			next_pos[x].pop()
			continue
		if len(next_pos[a]) == 0:
			a = x
			next_pos[a].pop()
			mn += 1
			continue
		if len(next_pos[b]) == 0:
			b = x
			next_pos[b].pop()
			mn += 1
			continue
		if next_pos[a][-1] <= next_pos[b][-1]:
			mn += 1
			b = x
			next_pos[b].pop()
			continue
		else:
			mn += 1
			a = x
			next_pos[a].pop()
			continue
	stdout.write(str(mn) + '\n')
main()


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')
from collections import Counter, defaultdict
import math
for _ in range(1):
	n = int(input())
	arr = list(map(int, input().split()))
	s = set()
	s.add(arr[0])
	last = arr[0]
	ans = 1
	for i in arr[1:]:
		if i == last:
			continue
		if i in s:
			s = {i, last}
		else:
			s.add(i)
			last = i
			ans += 1
	print(ans)


n = int(input())
arr = [int(x) for x in input().split()]
nxt = [0] * n
lst = [n + 1] * (n + 1)
for i in range(n - 1, -1, -1):
	nxt[i] = lst[arr[i]]
	lst[arr[i]] = i
(x, y, i, j, ans) = (0, 0, -1, -1, 0)
for (ind, elem) in enumerate(arr):
	if x == elem:
		i = ind
	elif y == elem:
		j = ind
	else:
		nx = n + 1 if i == -1 else nxt[i]
		ny = n + 1 if j == -1 else nxt[j]
		if nx > ny:
			x = elem
			i = ind
		else:
			y = elem
			j = ind
		ans += 1
print(ans)


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop
import math
from collections import *
from itertools import accumulate
from functools import reduce, cmp_to_key, lru_cache
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import sys
M = mod = 10 ** 9 + 7

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip().split()]

def st():
	return str(input().rstrip())[2:-1]

def val():
	return int(input().rstrip())

def li2():
	return [str(i)[2:-1] for i in input().rstrip().split()]

def li3():
	return [int(i) for i in st()]
n = val()
l = li()
cnt1 = cnt2 = 0
last1 = -float('inf')
last2 = -1

def compress(l):
	l1 = []
	for i in l:
		if len(l1) and l1[-1] == i:
			continue
		l1.append(i)
	return l1
l = compress(l)
if len(l) < 2:
	print(1)
	exit()
index = defaultdict(deque)
for i in range(len(l)):
	index[l[i]].append(i)
inset = set()
myset = set()
ans = 2
myset.add(l[0])
myset.add(l[1])
index[l[0]].popleft()
index[l[1]].popleft()
for i in range(2, len(l)):
	index[l[i]].popleft()
	if l[i] in myset:
		continue
	ans += 1
	(first, second) = (myset.pop(), myset.pop())
	myset.add(l[i])
	if index[first] and index[second]:
		if index[first][0] < index[second][0]:
			myset.add(first)
		else:
			myset.add(second)
	elif index[first]:
		myset.add(first)
	else:
		myset.add(second)
print(ans)


from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
nx_pos = [float('inf')] * n
dic = defaultdict(lambda : float('inf'))
for i in range(n - 1, -1, -1):
	nx_pos[i] = dic[a[i]]
	dic[a[i]] = i
(b, w) = ([(-1, -1)], [(-1, -1)])
ans = 0
for i in range(n):
	x = a[i]
	if b[-1][0] == x and w[-1][0] != x:
		b.append((x, i))
	elif w[-1][0] == x and b[-1][0] != x:
		w.append((x, i))
	elif w[-1][0] != x and b[-1][0] != x:
		na = nx_pos[b[-1][1]]
		nb = nx_pos[w[-1][1]]
		if na < nb:
			w.append((x, i))
		else:
			b.append((x, i))
		ans += 1
	else:
		w.append((x, i))
print(ans)


def compact(array):
	result = []
	array.append(-1)
	for i in range(len(array) - 1):
		if array[i] != array[i + 1]:
			result.append(array[i])
	return result
n = int(input())
a = list(map(int, input().split()))
data = compact(a)
result = 0
last_group = -1
between = []
last = {}
for (i, el) in enumerate(data):
	if el not in last:
		result += 1
	else:
		piece = data[last[el] + 1:i]
		if len(set(piece)) != len(piece):
			result += 1
		else:
			prev = last[data[i - 1]]
			last = {data[i - 1]: prev}
	last[el] = i
print(result)


n = int(input())
flist = list(map(int, input().split()))
res = 0
(min_value, mset) = (1, set(['@']))
for i in range(1, n):
	flag = 1 if flist[i] in mset else 0
	if flist[i] != flist[i - 1]:
		if flag:
			mset.clear()
		else:
			min_value += 1
		mset.add(flist[i - 1])
	elif flag:
		mset.add(flist[i - 1])
print(min_value)


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()
	B = getInts()
	next_ind = [-1] * (N + 1)
	last_seen = [-1] * (N + 1)
	for i in range(N - 1, -1, -1):
		next_ind[i] = last_seen[B[i]]
		last_seen[B[i]] = i
	(new1, new2) = (-1, -1)
	(new1_ind, new2_ind) = (-1, -1)
	ans = 0
	for i in range(N):
		if new1 == -1:
			assert new2 == -1
			new1 = B[i]
			new1_ind = next_ind[i]
			ans += 1
		elif B[i] == new1:
			new1_ind = next_ind[i]
			continue
		elif new2 == -1:
			new2 = B[i]
			new2_ind = next_ind[i]
			ans += 1
		elif B[i] == new2:
			new2_ind = next_ind[i]
			continue
		else:
			assert B[i] != new1 and B[i] != new2
			x = new1_ind
			y = new2_ind
			if x == -1:
				new1 = B[i]
				new1_ind = next_ind[i]
				ans += 1
				continue
			if y == -1:
				new2 = B[i]
				new2_ind = next_ind[i]
				ans += 1
				continue
			if x < y:
				new2 = B[i]
				new2_ind = next_ind[i]
				ans += 1
				continue
			if y < x:
				new1 = B[i]
				new1_ind = next_ind[i]
				ans += 1
				continue
	return ans
print(solve())


from sys import stdin, stdout
from collections import deque

def painting_the_array_2(n, a_a):
	dic = {}
	ua_a = [a_a[0]]
	dic[a_a[0]] = deque()
	dic[a_a[0]].append(0)
	for i in range(1, n):
		if a_a[i] == a_a[i - 1]:
			continue
		ua_a.append(a_a[i])
		if a_a[i] not in dic:
			dic[a_a[i]] = deque()
		dic[a_a[i]].append(i)
	r = 0
	one = -1
	two = -1
	for a in ua_a:
		if one == a:
			one = a
		elif two == a:
			two = a
		elif one == -1:
			one = a
			r += 1
		elif two == -1:
			two = a
			r += 1
		else:
			if len(dic[one]) == 0:
				one = a
			elif len(dic[two]) == 0:
				two = a
			elif dic[one][0] > dic[two][0]:
				one = a
			else:
				two = a
			r += 1
		dic[a].popleft()
	return r
n = int(stdin.readline())
a_a = list(map(int, stdin.readline().split()))
r = painting_the_array_2(n, a_a)
stdout.write(str(r))


import sys
input = sys.stdin.readline
n = int(input())
l = input().split()
li = [int(i) for i in l]
hashi = dict()
next = [0 for i in range(n)]
for i in range(n - 1, -1, -1):
	if li[i] not in hashi:
		next[i] = n
	else:
		next[i] = hashi[li[i]]
	hashi[li[i]] = i
ok = list(next)
next = dict()
for i in range(n):
	next[i] = ok[i]
next[-1] = n
ans = 0
curra = (-1, -1)
currb = (-1, -1)
for i in range(n):
	if li[i] == curra[0]:
		if li[i] == currb[0]:
			curra = (li[i], i)
			currb = (li[i], i)
			continue
		curra = (li[i], i)
		continue
	if li[i] == currb[0]:
		currb = (li[i], i)
		continue
	if next[curra[1]] >= next[currb[1]]:
		ans += 1
		curra = (li[i], i)
	else:
		ans += 1
		currb = (li[i], i)
print(ans)


n = int(input())
aa = [int(x) for x in input().split()]
choices = set()
i = 0
segcount = 0
(c1, c0) = (-1, -1)
state = None
while i < n:
	a = aa[i]
	if len(choices) < 2:
		if a in choices:
			pass
		else:
			choices.add(a)
			segcount += 1
	elif a in choices:
		if state == a:
			pass
		elif i >= 1 and aa[i] == aa[i - 1]:
			pass
		else:
			choices.clear()
			choices.add(a)
			choices.add(aa[i - 1])
			state = a
	else:
		choices.add(a)
		segcount += 1
		state = None
	i += 1
print(segcount)