problem

There are the following games.

N characters are lined up in a vertical row. The color of these characters is red, blue, or yellow, and in the initial state, four or more characters of the same color are not lined up in a row. The player can select a character at a certain position and change it to another color. By this operation, if four or more characters of the same color are lined up in a row, those characters will disappear. When four or more characters of the same color are lined up in a row due to the disappearance of the characters, those characters also disappear, and this chain continues until there are no more places where four or more characters of the same color are lined up in a row. .. The purpose of this game is to reduce the number of characters remaining without disappearing.

For example, if the color of the sixth character from the top is changed from yellow to blue in the state at the left end of the figure below, five blue characters will disappear in a row, and finally three characters will remain without disappearing.

<image>


Given the color sequence of N characters in the initial state, create a program that finds the minimum value M of the number of characters that remain without disappearing when the color of the character is changed in only one place.



input

The input consists of multiple datasets. Each dataset is given in the following format.

The first line consists of only the number of characters N (1 ≤ N ≤ 10000). The following N lines contain one of 1, 2, and 3 integers, and the i + 1st line (1 ≤ i ≤ N) represents the color of the i-th character from the top in the initial state (1). Is red, 2 is blue, and 3 is yellow).

When N is 0, it indicates the end of input. The number of datasets does not exceed 5.

output

For each dataset, output the minimum value M of the number of characters remaining without disappearing on one line.

Examples

Input

12
3
2
1
1
2
3
2
2
2
1
1
3
12
3
2
1
1
2
3
2
1
3
2
1
3
0


Output

3
12


Input

None


Output

None

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
def erase(array, i, N):
	if array[i - 1] == array[i]:
		up = i - 1
		down = i
	elif array[i] == array[i + 1]:
		up = i
		down = i + 1
	else:
		return N - 2
	while True:
		if array[up] == -1 or array[down] == -1 or (not array[up] == array[down]):
			return up + N - down - 1
		save_up = up
		save_down = down
		c = array[up]
		while array[up] == c:
			up -= 1
		while array[down] == c:
			down += 1
		if save_up - up + down - save_down < 4:
			return save_up + N - save_down - 1

def main():
	while True:
		N = int(input())
		if N == 0:
			return
		a = [-1]
		for i in range(N):
			a.append(int(input()))
		a.append(-1)
		min_erased = N
		for i in range(1, N + 1):
			save = a[i]
			a[i] = save % 3 + 1
			min_erased = min(min_erased, erase(a, i, N + 2))
			a[i] = (save + 1) % 3 + 1
			min_erased = min(min_erased, erase(a, i, N + 2))
			a[i] = save
		print(min_erased)
main()


def doChain(ar, si, ei):
	(p, c) = (0, [])
	for i in range(si, ei):
		if ar[i] == p:
			c.append(i)
			if i == len(ar) - 1 and len(c) >= 4:
				del ar[min(c):max(c) + 1]
				return (True, max(0, si - 3), min(ei + 5, len(ar)))
		else:
			if len(c) >= 4:
				del ar[min(c):max(c) + 1]
				return (True, max(0, si - 3), min(ei + 5, len(ar)))
			p = ar[i]
			c = [i]
	return (False, 0, len(ar))
while True:
	N = int(input())
	if N == 0:
		break
	A = [int(input()) for _ in range(N)]
	minvalue = N
	for j in range(len(A) - 1):
		B = A[:]
		if B[j + 1] != B[j]:
			B[j + 1] = B[j]
			result = True
			(si, ei) = (max(0, j - 3), min(j + 5, len(A)))
			while result == True:
				(result, si, ei) = doChain(B, si, ei)
				if len(B) < minvalue:
					minvalue = len(B)
	print(minvalue)


def solve():
	INF = 100000
	while True:
		n = int(input())
		if not n:
			break
		lst = [int(input()) for _ in range(n)]

		def check(x):
			c = lst[x]
			l = r = x
			b = 0
			for i in range(r, n):
				if lst[i] != c:
					r = i - 1
					break
			else:
				r = n - 1
			for i in range(l, -1, -1):
				if lst[i] != c:
					l = i + 1
					break
			else:
				l = 0
			if r - l - b < 3:
				return n
			else:
				b = r - l
			while l > 0 and r < n - 1:
				c = lst[l - 1]
				if c != lst[r + 1]:
					break
				else:
					for i in range(r + 1, n):
						if lst[i] != c:
							r = i - 1
							break
					else:
						r = n - 1
					for i in range(l - 1, -1, -1):
						if lst[i] != c:
							l = i + 1
							break
					else:
						l = 0
					if r - l - b < 4:
						break
					else:
						b = r - l
			return n - (b + 1)
		ans = INF
		for i in range(n):
			lst[i] = lst[i] % 3 + 1
			ans = min(ans, check(i))
			lst[i] = lst[i] % 3 + 1
			ans = min(ans, check(i))
			lst[i] = lst[i] % 3 + 1
		print(ans)
solve()


def solve():
	INF = 100000
	while True:
		n = int(input())
		if not n:
			break
		lst = [int(input()) for _ in range(n)]

		def check(x):
			c1 = c2 = lst[x]
			l = r = x
			b = 0
			for i in range(r, n):
				if lst[i] != c2:
					r = i - 1
					break
			else:
				r = n - 1
			for i in range(l, -1, -1):
				if lst[i] != c1:
					l = i + 1
					break
			else:
				l = 0
			if r - l - b < 3:
				return n
			else:
				b = r - l
			while l > 0 and r < n - 1:
				c1 = lst[l - 1]
				c2 = lst[r + 1]
				if c1 != c2:
					break
				else:
					for i in range(r + 1, n):
						if lst[i] != c2:
							r = i - 1
							break
					else:
						r = n - 1
					for i in range(l - 1, -1, -1):
						if lst[i] != c1:
							l = i + 1
							break
					else:
						l = 0
					if r - l - b < 4:
						break
					else:
						b = r - l
			return n - (b + 1)
		ans = INF
		for i in range(n):
			lst[i] = (lst[i] + 1) % 3 + 1
			ans = min(ans, check(i))
			lst[i] = (lst[i] + 1) % 3 + 1
			ans = min(ans, check(i))
			lst[i] = (lst[i] + 1) % 3 + 1
		print(ans)
solve()


def cara(n):
	kazu = []
	ilo = []
	a = int(input())
	una = a
	kazu.append(1)
	ilo.append(a)
	for n in range(n - 1):
		a = int(input())
		if una == a:
			kazu[-1] += 1
		else:
			kazu.append(1)
			ilo.append(a)
			una = a
	return (ilo, kazu)

def kes(ilo, kazu):
	k = 10000
	unanseer = sum(kazu)
	anseer = sum(kazu)
	for p in range(len(ilo)):
		n = 0
		if kazu[p] >= 3:
			anseer = kurabe(ilo, kazu, p)
		n = 0
		if p + 2 < len(ilo) and ilo[p] == ilo[p + 2] and (kazu[p] + kazu[p + 2] >= 3) and (kazu[p + 1] == 1):
			while p + 2 + n < len(ilo) and p - n >= 0 and (ilo[p - n] == ilo[p + 2 + n]) and (kazu[p - n] + kazu[p + 2 + n] >= 4):
				n += 1
			if n > 2500:
				print(n)
			unanseer = kensa(ilo, kazu, n, p)
		if unanseer < anseer:
			anseer = unanseer
		if anseer < k:
			k = anseer
	return k

def kensa(ilo, kazu, n, p):
	k = 0
	if n == 0:
		for w in range(len(kazu)):
			k += kazu[w]
	else:
		for q in range(0, p - n + 1):
			k += kazu[q]
		for i in range(p + 2 + n, len(kazu)):
			k += kazu[i]
	return k

def kurabe(ilo, kazu, p):
	n = 0
	a = 0
	b = 0
	k = 0
	if p + 1 < len(ilo):
		kazu[p + 1] -= 1
		kazu[p] += 1
		while 0 < p - a and len(kazu) > p + 1 + a and (ilo[p + 1 + a] == ilo[p - 1 - a]) and (kazu[p + 1 + a] + kazu[p - 1 - a] >= 4):
			a += 1
		kazu[p + 1] += 1
		kazu[p] -= 1
	if p - 1 >= 0:
		kazu[p - 1] -= 1
		kazu[p] += 1
		while len(kazu) > p + 1 + b and 0 < p - b and (ilo[p + b + 1] == ilo[p - 1 - b]) and (kazu[p + b + 1] + kazu[p - 1 - b] >= 4):
			b += 1
		kazu[p - 1] += 1
		kazu[p] -= 1
	if a < b:
		n = b
	else:
		n = a
	for q in range(0, p - n):
		k += kazu[q]
	for i in range(p + n, len(kazu)):
		k += kazu[i]
	k -= 3
	return k
while True:
	n = int(input())
	if n == 0:
		break
	(ilo, kazu) = cara(n)
	print(kes(ilo, kazu))


def myinput(n):
	C = [int(input())]
	L = [1]
	for i in range(1, n):
		c = int(input())
		if C[-1] == c:
			L[-1] += 1
		else:
			C.append(c)
			L.append(1)
	return [C, L]

def check(C, L, low, hih):
	m = len(C)
	ret = 0
	if 0 <= low and L[low] >= 4 and (hih >= m or C[low] != C[hih]):
		ret += L[low]
		low -= 1
	if hih < m and L[hih] >= 4 and (low < 0 or C[low] != C[hih]):
		ret += L[hih]
		hih += 1
	while 0 <= low and hih < m and (C[low] == C[hih]) and (L[low] + L[hih] >= 4):
		ret += L[low] + L[hih]
		low -= 1
		hih += 1
	return ret

def solve(C, L):
	m = len(C)
	ret = 0
	for i in range(m):
		L[i] -= 1
		if i + 1 < m:
			L[i + 1] += 1
			if L[i] > 0:
				ret = max(ret, check(C, L, i, i + 1))
			else:
				ret = max(ret, check(C, L, i - 1, i + 1))
			L[i + 1] -= 1
		if i - 1 >= 0:
			L[i - 1] += 1
			if L[i] > 0:
				ret = max(ret, check(C, L, i - 1, i))
			else:
				ret = max(ret, check(C, L, i - 1, i + 1))
			L[i - 1] -= 1
		L[i] += 1
	return ret
while True:
	n = int(input())
	if n == 0:
		break
	(C, L) = myinput(n)
	print(n - solve(C, L))


INF = 100000
while True:
	n = int(input())
	if not n:
		break
	lst = [int(input()) for _ in range(n)]

	def check(x):
		c1 = c2 = lst[x]
		l = r = x
		b = 0
		for i in range(r, n):
			if lst[i] != c2:
				r = i - 1
				break
		else:
			r = n - 1
		for i in range(l, -1, -1):
			if lst[i] != c1:
				l = i + 1
				break
		else:
			l = 0
		if r - l - b < 3:
			return n
		else:
			b = r - l
		while l > 0 and r < n - 1:
			c1 = lst[l - 1]
			c2 = lst[r + 1]
			if c1 != c2:
				break
			else:
				for i in range(r + 1, n):
					if lst[i] != c2:
						r = i - 1
						break
				else:
					r = n - 1
				for i in range(l - 1, -1, -1):
					if lst[i] != c1:
						l = i + 1
						break
				else:
					l = 0
				if r - l - b < 4:
					break
				else:
					b = r - l
		return n - (b + 1)
	ans = INF
	for i in range(n):
		lst[i] = (lst[i] + 1) % 3 + 1
		ans = min(ans, check(i))
		lst[i] = (lst[i] + 1) % 3 + 1
		ans = min(ans, check(i))
		lst[i] = (lst[i] + 1) % 3 + 1
	print(ans)


while True:
	n = int(input())
	if not n:
		break
	puyos = []
	pre = int(input())
	cnt = 1
	for _ in range(n - 1):
		p = int(input())
		if pre != p:
			puyos.append((pre, cnt))
			pre = p
			cnt = 0
		cnt += 1
	puyos.append((pre, cnt))
	lp = len(puyos)
	min_puyo = n
	for (i, puyo) in enumerate(puyos):
		(color, num) = puyo
		if num == 2:
			continue
		(tn, j) = (n, 1)
		while True:
			if i - j < 0 or i + j >= lp:
				break
			(tp_c, tp_n) = puyos[i - j]
			(up_c, up_n) = puyos[i + j]
			if tp_c != up_c:
				break
			first_adjust = 0
			if j == 1:
				if num == 1:
					first_adjust = 1
				else:
					first_adjust = -1
					tn -= 4
			dp = tp_n + up_n + first_adjust
			if dp < 4:
				break
			tn -= dp
			j += 1
		if min_puyo > tn:
			min_puyo = tn
	print(min_puyo)