You are given a line of $n$ colored squares in a row, numbered from $1$ to $n$ from left to right. The $i$-th square initially has the color $c_i$.

Let's say, that two squares $i$ and $j$ belong to the same connected component if $c_i = c_j$, and $c_i = c_k$ for all $k$ satisfying $i < k < j$. In other words, all squares on the segment from $i$ to $j$ should have the same color.

For example, the line $[3, 3, 3]$ has $1$ connected component, while the line $[5, 2, 4, 4]$ has $3$ connected components.

The game "flood fill" is played on the given line as follows:   At the start of the game you pick any starting square (this is not counted as a turn).  Then, in each game turn, change the color of the connected component containing the starting square to any other color. 

Find the minimum number of turns needed for the entire line to be changed into a single color.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 5000$) — the number of squares.

The second line contains integers $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le 5000$) — the initial colors of the squares.


-----Output-----

Print a single integer — the minimum number of the turns needed.


-----Examples-----
Input
4
5 2 2 1

Output
2

Input
8
4 5 2 2 1 3 5 5

Output
4

Input
1
4

Output
0



-----Note-----

In the first example, a possible way to achieve an optimal answer is to pick square with index $2$ as the starting square and then play as follows:  $[5, 2, 2, 1]$  $[5, 5, 5, 1]$  $[1, 1, 1, 1]$ 

In the second example, a possible way to achieve an optimal answer is to pick square with index $5$ as the starting square and then perform recoloring into colors $2, 3, 5, 4$ in that order.

In the third example, the line already consists of one color only.

Difficulty: HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
n = int(input())
lsr = list(map(int, input().split()))
ls = [lsr[0]]
for le in lsr[1:]:
	if le != ls[-1]:
		ls.append(le)
n = len(ls)
dpa = []
dpb = [0 for i in range(n + 1)]
for sz in range(2, n + 1):
	dp = []
	for start in range(n - sz + 1):
		if ls[start] == ls[start + sz - 1]:
			dp.append(min(dpb[start], dpb[start + 1], dpa[start + 1]) + 1)
		else:
			dp.append(min(dpb[start], dpb[start + 1]) + 1)
	(dpa, dpb) = (dpb, dp)
print(dpb[0])


import collections
import time
import os
import sys
import bisect
import heapq

def solve(N, C):
	A = []
	for c in C:
		if not A or A[-1] != c:
			A.append(c)
	colors = list(set(C))
	colors.sort()
	cmap = {c: i + 1 for (i, c) in enumerate(colors)}
	A = [cmap[a] for a in A]
	N = len(A)
	C = len(colors)
	dp = [[[float('inf') for _ in range(2)] for _ in range(N + 1)] for _ in range(N + 1)]
	for i in range(N):
		dp[i][i][0] = 0
		dp[i][i][1] = 0
	for r in range(N):
		for l in range(r, -1, -1):
			for i in range(2):
				c = A[l] if i == 0 else A[r]
				if l:
					dp[l - 1][r][0] = min(dp[l - 1][r][0], dp[l][r][i] + (1 if c != A[l - 1] else 0))
				if r + 1 < N:
					dp[l][r + 1][1] = min(dp[l][r + 1][1], dp[l][r][i] + (1 if c != A[r + 1] else 0))
	print(min(dp[0][N - 1]))

def solve2(N, C):
	A = []
	for c in C:
		if not A or A[-1] != c:
			A.append(c)
	B = A[::-1]
	N = len(A)
	dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
	for i in range(1, N + 1):
		for j in range(1, N + 1):
			dp[i][j] = dp[i - 1][j - 1] + 1 if A[i - 1] == B[j - 1] else max(dp[i - 1][j], dp[i][j - 1])
	print(N - 1 - dp[N][N] // 2)
N = int(input())
C = [int(x) for x in input().split()]
solve2(N, C)


def lps(str):
	n = len(str)
	L = [[0 for x in range(n)] for x in range(n)]
	for i in range(n):
		L[i][i] = 1
	for cl in range(2, n + 1):
		for i in range(n - cl + 1):
			j = i + cl - 1
			if str[i] == str[j] and cl == 2:
				L[i][j] = 2
			elif str[i] == str[j]:
				L[i][j] = L[i + 1][j - 1] + 2
			else:
				L[i][j] = max(L[i][j - 1], L[i + 1][j])
	return L[0][n - 1]
n = input()
n = int(n)
l = list(map(str, input().strip().split()))
seq = [l[0]]
ch = l[0]
for i in range(1, n):
	if l[i] != ch:
		ch = l[i]
		seq.append(l[i])
n = len(seq)
print(n - lps(seq) // 2 - 1)


n = int(input())
c = list(map(int, input().split()))
c.append(-5)
arr = [0]
for i in range(n):
	if c[i] != c[i + 1]:
		arr.append(c[i])
arr_r = [0] + arr[::-1]
l = len(arr)
store = [0] * l
up = [0] * l
for i in range(1, l):
	for j in range(1, l):
		if arr[i] == arr_r[j]:
			store[j] = up[j - 1] + 1
		else:
			store[j] = max(store[j - 1], up[j])
	up = store
	store = [0] * l
print(l - 1 - 1 - up[-1] // 2)


a = int(input())
b = [int(x) for x in input().split()]
c = [b[0]]
for i in b[1:]:
	if i != c[-1]:
		c.append(i)
a = len(c)
dpa = []
dpb = [0] * (a + 1)
for i in range(2, a + 1):
	dp = []
	for j in range(a - i + 1):
		if c[j] == c[j + i - 1]:
			dp.append(min(dpb[j], dpb[j + 1], dpa[j + 1]) + 1)
		else:
			dp.append(min(dpb[j], dpb[j + 1]) + 1)
	(dpa, dpb) = (dpb, dp)
print(dpb[0])


n = int(input())
C = [0] + list(map(int, input().split()))
A = []
for i in range(1, n + 1):
	if C[i] != C[i - 1]:
		A.append(C[i])
L = len(A)
DP = [[[0] * L for i in range(L)] for j in range(2)]

def color(r, i, j):
	if r == 1:
		if A[i] == A[j]:
			DP[r][i][j] = min(DP[0][i][j - 1], DP[1][i][j - 1] + 1)
		else:
			DP[r][i][j] = min(DP[0][i][j - 1] + 1, DP[1][i][j - 1] + 1)
	elif A[i] == A[j]:
		DP[r][i][j] = min(DP[1][i + 1][j], DP[0][i + 1][j] + 1)
	else:
		DP[r][i][j] = min(DP[1][i + 1][j] + 1, DP[0][i + 1][j] + 1)
for i in range(1, L):
	for j in range(L - i):
		color(0, j, i + j)
		color(1, j, i + j)
print(min(DP[0][0][L - 1], DP[1][0][L - 1]))


def run_length_compress(string):
	string = string + ['.']
	n = len(string)
	begin = 0
	end = 1
	cnt = 1
	ans = []
	while True:
		if end >= n:
			break
		if string[begin] == string[end]:
			end += 1
			cnt += 1
		else:
			ans.append(string[begin])
			begin = end
			end = begin + 1
			cnt = 1
	return ans

def lps(string):
	n = len(string)
	dp = [[0] * n for _ in range(n)]
	for i in range(n):
		dp[i][i] = 1
	for cl in range(2, n + 1):
		for i in range(n - cl + 1):
			j = i + cl - 1
			if string[i] == string[j] and cl == 2:
				dp[i][j] = 2
			elif string[i] == string[j]:
				dp[i][j] = dp[i + 1][j - 1] + 2
			else:
				dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
	return dp[0][n - 1]
n = int(input())
a = list(map(int, input().split()))
a = run_length_compress(a)
len_pal = lps(a)
print(len(a) - 1 - len_pal // 2)


def inpl():
	return list(map(int, input().split()))
N = int(input())
A = inpl()
B = [0]
for a in A:
	if B[-1] != a:
		B.append(a)
B = B[1:]
k = len(B)
dp = [0] * ((k * k + k) // 2)
for d in range(1, k):
	for i in range(k - d):
		if B[i] == B[i + d]:
			dp[d * (2 * k - d + 1) // 2 + i] = dp[(d - 2) * (2 * k - d + 3) // 2 + i + 1] + 1
		else:
			dp[d * (2 * k - d + 1) // 2 + i] = 1 + min(dp[(d - 1) * (2 * k - d + 2) // 2 + i], dp[(d - 1) * (2 * k - d + 2) // 2 + i + 1])
print(dp[-1])


n = int(input())
raw_list = [int(item) for item in input().split()]
l = [raw_list[0]]
for item in raw_list[1:]:
	if item != l[-1]:
		l.append(item)
n = len(l)
dp1 = []
dp2 = [0] * (n + 1)
for i in range(2, n + 1):
	dp = []
	for j in range(n - i + 1):
		if l[j] == l[i + j - 1]:
			dp.append(min(dp1[j + 1], dp2[j], dp2[j + 1]) + 1)
		else:
			dp.append(min(dp2[j], dp2[j + 1]) + 1)
	(dp1, dp2) = (dp2, dp)
res = dp2[0]
print(res)


import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5:
	from math import gcd
else:
	from fractions import gcd
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

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

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

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

def round(x):
	return int((x * 2 + 1) // 2)

def fermat(x, y, MOD):
	return x * pow(y, MOD - 2, MOD) % MOD

def lcm(x, y):
	return x * y // gcd(x, y)

def lcm_list(nums):
	return reduce(lcm, nums, 1)

def gcd_list(nums):
	return reduce(gcd, nums, nums[0])

def INT():
	return int(input())

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

def LIST():
	return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7
N = INT()
cN = LIST()
cN2 = [cN[0]]
for i in range(1, N):
	if cN[i] != cN[i - 1]:
		cN2.append(cN[i])
cN3 = list(reversed(cN2))
N2 = len(cN2)
dp = [[0] * (N2 + 1) for i in range(N2 + 1)]
for i in range(N2 + 1):
	for j in range(N2 + 1):
		if i < N2:
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
		if j < N2:
			dp[i][j + 1] = max(dp[i][j + 1], dp[i][j])
		if i < N2 and j < N2 and (cN2[i] == cN3[j]):
			dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
print(N2 - 1 - dp[N2][N2] // 2)


import sys
from atexit import register
from io import BytesIO, FileIO, StringIO
sys.stdin = BytesIO(FileIO(0).read())
input = lambda : sys.stdin.readline()
sys.stdout = StringIO()
register(lambda : FileIO(1, 'w').write(sys.stdout.getvalue().encode()))

def main():
	n = int(input())
	a = input().split()
	dp = [[[5000] * n for _ in range(n)] for _ in range(2)]
	for i in range(n):
		(dp[0][i][i], dp[1][i][i]) = (0, 0)
	for r in range(n):
		for l in range(r, -1, -1):
			for it in range(2):
				c = a[l] if it == 0 else a[r]
				if l != 0:
					dp[0][l - 1][r] = min(dp[0][l - 1][r], dp[it][l][r] + (1 if c != a[l - 1] else 0))
				if r != n - 1:
					dp[1][l][r + 1] = min(dp[1][l][r + 1], dp[it][l][r] + (1 if c != a[r + 1] else 0))
	print(min(dp[0][0][n - 1], dp[1][0][n - 1]))
main()


from itertools import groupby
import math
(n,) = list(map(int, input().strip().split()))
array = list(map(int, input().strip().split()))
g_array = [k for (k, g) in groupby(array)]
n = len(g_array)
extend_n = n + 2
sols = [[0] * extend_n for _ in range(extend_n)]
for i in range(1, extend_n - 1):
	for j in range(extend_n - 2, i, -1):
		val = max(sols[i - 1][j], sols[i][j + 1])
		if g_array[i - 1] == g_array[j - 1]:
			val = max(val, sols[i - 1][j + 1] + 1)
		sols[i][j] = val
best = 0
for start in range(1, extend_n - 1 - 1):
	start_val = sols[start - 1][start + 1]
	if start_val > best:
		best = start_val
print(len(g_array) - 1 - best)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import deque
import threading
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 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 main():
	n = int(input())
	arr = list(map(int, input().split()))
	p = 0
	for i in range(n):
		if arr[i] != arr[p]:
			p += 1
			arr[p] = arr[i]
	n = p + 1
	pre = [0 for _ in range(n)]
	dp = [n for _ in range(n)]
	for i in range(n):
		dp[i] = 0
	for i in range(2, n + 1):
		new = [n for _ in range(n - i + 1)]
		for l in range(n - i + 1):
			r = l + i - 1
			if arr[l] == arr[r]:
				now = min(new[l], pre[l + 1] + 1)
				new[l] = now
			else:
				new[l] = min(new[l], min(dp[l + 1], dp[l]) + 1)
		pre = dp
		dp = new
	print(dp[0])
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 math import factorial
from collections import Counter, defaultdict
from heapq import heapify, heappop, heappush

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 comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

def main():
	n = N()
	arr = RLL()
	narr = [arr[0]]
	for i in range(1, n):
		if arr[i] != narr[-1]:
			narr.append(arr[i])
	arr = narr
	n = len(arr)
	dp = [[n for _ in range(n)] for _ in range(n)]
	for i in range(n):
		dp[i][i] = 0
	for i in range(2, n + 1):
		for l in range(n - i + 1):
			r = l + i - 1
			if arr[l] == arr[r]:
				dp[l][r] = dp[l + 1][r - 1] + 1
			else:
				dp[l][r] = min(dp[l][r], min(dp[l + 1][r], dp[l][r - 1]) + 1)
	print(dp[0][-1])
main()


import sys
from atexit import register
from io import StringIO
from os import fstat, read, write
input = StringIO(read(0, fstat(0).st_size).decode()).readline
sys.stdout = StringIO()
register(lambda : write(1, sys.stdout.getvalue().encode()))

def main():
	n = int(input())
	a = input().split()
	dp = [[[5000] * n for _ in range(n)] for _ in range(2)]
	for i in range(n):
		(dp[0][i][i], dp[1][i][i]) = (0, 0)
	for r in range(n):
		for l in range(r, -1, -1):
			for it in range(2):
				c = a[l] if it == 0 else a[r]
				if l != 0:
					dp[0][l - 1][r] = min(dp[0][l - 1][r], dp[it][l][r] + (1 if c != a[l - 1] else 0))
				if r != n - 1:
					dp[1][l][r + 1] = min(dp[1][l][r + 1], dp[it][l][r] + (1 if c != a[r + 1] else 0))
	print(min(dp[0][0][n - 1], dp[1][0][n - 1]))
main()


n = int(input())
(*a,) = map(int, input().split())
a.append(-1)
b = [a[i] for i in range(n) if a[i] != a[i - 1]]
dp = [[0 for j in range(n + 2)] for i in range(n + 2)]
for l in range(len(b)):
	for i in range(len(b) - l):
		j = i + l
		dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
		if b[i] == b[j]:
			dp[i][j] = dp[i + 1][j - 1] + 2
print(len(b) - (dp[0][len(b) - 1] + 1) // 2)


def fill():
	nonlocal dp
	dp = [0] * (n + 2)
	for i in range(n + 2):
		dp[i] = [0] * (n + 2)

def compress(v):
	nonlocal n
	nonlocal c
	c = [v[0]]
	for i in range(1, n):
		if v[i] != v[i - 1]:
			c.append(v[i])
	n = len(c)
n = int(input())
v = [int(i) for i in input().split()]
c = []
compress(v)
dp = []
fill()
for i in range(n):
	dp[i][1] = 0
	dp[i][2] = 1
for sz in range(3, n + 1):
	for i in range(n):
		j = i + sz - 1
		if j >= n:
			break
		if c[i] == c[j]:
			dp[i][sz] = dp[i + 1][sz - 2] + 1
		else:
			dp[i][sz] = min(dp[i + 1][sz - 1], dp[i][sz - 1]) + 1
print(dp[0][n])


n = int(input())
C = [int(i) for i in input().split()]
D = []
for c in C:
	if not D or D[-1] != c:
		D.append(c)
n = len(D)
C = D[::-1]
DP = [[0] * (n + 1) for i in range(2)]
for i in range(n):
	for j in range(n):
		if C[i] == D[j]:
			DP[i + 1 & 1][j + 1] = DP[i & 1][j] + 1
		else:
			DP[i + 1 & 1][j + 1] = max(DP[i + 1 & 1][j], DP[i & 1][j + 1])
print(n - 1 - DP[n & 1][n] // 2)


def lcs(a, b):
	c = [[0 for i in range(len(a) + 1)] for i in range(len(b) + 1)]
	for i in range(len(b) + 1):
		for j in range(len(b) + 1):
			if i == 0 or j == 0:
				c[i][j] = 0
			elif a[i - 1] == b[j - 1]:
				c[i][j] = c[i - 1][j - 1] + 1
			else:
				c[i][j] = max(c[i - 1][j], c[i][j - 1])
	return c
n = int(input())
a = list(map(int, input().split()))
b = [a[0]]
for i in range(1, n):
	if a[i] != a[i - 1]:
		b.append(a[i])
a = b[::-1]
c = lcs(a, b)
ans = 0
n = len(a)
for i in range(0, n + 1):
	ans = max(ans, c[i][n - i])
print(n - ans - 1)


import sys
input = sys.stdin.readline
n = int(input())
c = list(map(int, input().split())) + [-1]
b = [c[i] for i in range(n) if c[i] != c[i + 1]]
m = len(b)
INF = 10 ** 9
dp = [[[INF] * (m + 1) for i in range(m + 1)] for j in range(2)]
for i in range(m):
	dp[0][i][i] = dp[1][i][i] = 0
for l in range(1, m):
	for i in range(m - l):
		j = i + l
		dp[0][i][j] = min(dp[0][i][j], dp[0][i + 1][j] + (b[i] != b[i + 1]), dp[1][i + 1][j] + (b[i] != b[j]))
		dp[1][i][j] = min(dp[1][i][j], dp[0][i][j - 1] + (b[i] != b[j]), dp[1][i][j - 1] + (b[j - 1] != b[j]))
print(min(dp[1][0][m - 1], dp[0][0][m - 1]))


def solve(a):
	n = len(a)
	best = [[0] * n for _ in range(n)]
	for i in range(n - 1, -1, -1):
		for j in range(i + 1, n):
			if a[i] == a[j]:
				best[i][j] = best[i + 1][j - 1] + 1
			else:
				best[i][j] = min(best[i + 1][j], best[i][j - 1]) + 1
	return best[0][n - 1]
n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
	if i == 0 or a[i - 1] != a[i]:
		b.append(a[i])
print(solve(b))


def main():
	for i in range(n):
		for j in range(n):
			dp[0][i][j] = dp[1][i][j] = 0 if i == j else n
	for r in range(n):
		for l in range(r, -1, -1):
			for k in [0, 1]:
				color = c[l] if k == 0 else c[r]
				if l != 0:
					dp[0][l - 1][r] = min(dp[0][l - 1][r], dp[k][l][r] + (1 if color != c[l - 1] else 0))
				if r + 1 != n:
					dp[1][l][r + 1] = min(dp[1][l][r + 1], dp[k][l][r] + (1 if color != c[r + 1] else 0))
	print(min(dp[0][0][n - 1], dp[1][0][n - 1]))
n = int(input())
c = list(map(int, input().split()))
dp = [[[0] * n for _ in range(n)] for _ in range(2)]
main()


n = int(input())
a = list(map(int, input().split()))
b = []
p = -1
for e in a:
	if e == p:
		continue
	else:
		b.append(e)
		p = e

def lcs(a, b):
	lengths = [[0 for j in range(len(b) + 1)] for i in range(len(a) + 1)]
	for (i, x) in enumerate(a):
		for (j, y) in enumerate(b):
			if x == y:
				lengths[i + 1][j + 1] = lengths[i][j] + 1
			else:
				lengths[i + 1][j + 1] = max(lengths[i + 1][j], lengths[i][j + 1])
	(x, y) = (len(a), len(b))
	return lengths[x][y]
ans = 0
ans = lcs(list(reversed(b)), b) // 2
n = len(b)
print(n - ans - 1)


from sys import stdin, stdout, setrecursionlimit
input = stdin.readline
inf = float('inf')
from functools import cmp_to_key
from collections import defaultdict as dd
from collections import Counter, deque
from heapq import *
import math
from math import floor, ceil, sqrt

def geti():
	return map(int, input().strip().split())

def getl():
	return list(map(int, input().strip().split()))

def getis():
	return map(str, input().strip().split())

def getls():
	return list(map(str, input().strip().split()))

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

def geta():
	return int(input())

def print_s(s):
	stdout.write(s + '\n')

def lca(a, b):
	n = len(a)
	dp = [[0] * (n + 1) for _ in range(n + 1)]
	for i in range(n):
		for j in range(n):
			if a[i] == b[j]:
				dp[i + 1][j + 1] = dp[i][j] + 1
			else:
				dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
	return dp[n][n]

def solve():
	n = geta()
	a = []
	for i in getl():
		if a and a[-1] == i:
			continue
		a.append(i)
	n = len(a)
	length = lca(a, a[::-1])
	print(n - (length + 1) // 2)
solve()


n = int(input())
C = [int(i) for i in input().split()]
INF = 5000
DP = [[[0] * 2 for i in range(n)] for j in range(2)]
for i in range(n - 1):
	for j in range(n - i - 1):
		DP[(i + 1) % 2][j][0] = INF
		DP[(i + 1) % 2][j][1] = INF
		for k in range(2):
			c = C[j] if k == 0 else C[j + i]
			if c == C[j + i + 1]:
				DP[(i + 1) % 2][j][1] = min(DP[(i + 1) % 2][j][1], DP[i % 2][j][k])
			else:
				DP[(i + 1) % 2][j][1] = min(DP[(i + 1) % 2][j][1], DP[i % 2][j][k] + 1)
			c = C[j + 1] if k == 0 else C[j + i + 1]
			if c == C[j]:
				DP[(i + 1) % 2][j][0] = min(DP[(i + 1) % 2][j][0], DP[i % 2][j + 1][k])
			else:
				DP[(i + 1) % 2][j][0] = min(DP[(i + 1) % 2][j][0], DP[i % 2][j + 1][k] + 1)
print(min(DP[(n - 1) % 2][0]))


from __future__ import division, print_function
import cmath
import itertools
import math
import operator as op
import sys
from atexit import register
from bisect import bisect_left, bisect_right
from io import BytesIO, FileIO, StringIO
if sys.version_info[0] < 3:

	class dict(dict):

		def items(self):
			return dict.iteritems(self)

		def keys(self):
			return dict.iterkeys(self)

		def values(self):
			return dict.itervalues(self)
	input = raw_input
	range = xrange
	filter = itertools.ifilter
	map = itertools.imap
	zip = itertools.izip
INP_FILE = 0
OUT_FILE = 1
if sys.version_info[0] < 3:
	sys.stdin = BytesIO(FileIO(INP_FILE).read())
	sys.stdout = BytesIO()
	register(lambda : FileIO(OUT_FILE, 'w').write(sys.stdout.getvalue()))
else:
	sys.stdin = StringIO(FileIO(INP_FILE).read().decode())
	sys.stdout = StringIO()
	register(lambda : FileIO(OUT_FILE, 'w').write(sys.stdout.getvalue().encode()))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def lcs(a, b):
	lengths = [[0] * (len(b) + 1) for i in range(len(a) + 1)]
	for (i, x) in enumerate(a):
		for (j, y) in enumerate(b):
			if x == y:
				lengths[i + 1][j + 1] = lengths[i][j] + 1
			else:
				lengths[i + 1][j + 1] = max(lengths[i + 1][j], lengths[i][j + 1])
	result = []
	(x, y) = (len(a), len(b))
	while x != 0 and y != 0:
		if lengths[x][y] == lengths[x - 1][y]:
			x -= 1
		elif lengths[x][y] == lengths[x][y - 1]:
			y -= 1
		else:
			result.append(a[x - 1])
			x -= 1
			y -= 1
	return len(result)

def main():
	input()
	c = ['']
	for i in input().split():
		if i != c[-1]:
			c.append(i)
	print(len(c) - (lcs(c, c[::-1]) + 1) // 2 - 1)
main()