Память компьютера состоит из n ячеек, которые выстроены в ряд. Пронумеруем ячейки от 1 до n слева направо. Про каждую ячейку известно, свободна она или принадлежит какому-либо процессу (в таком случае известен процесс, которому она принадлежит).

Для каждого процесса известно, что принадлежащие ему ячейки занимают в памяти непрерывный участок. С помощью операций вида «переписать данные из занятой ячейки в свободную, а занятую теперь считать свободной» требуется расположить все принадлежащие процессам ячейки в начале памяти компьютера. Другими словами, любая свободная ячейка должна располагаться правее (иметь больший номер) любой занятой.

Вам необходимо найти минимальное количество операций переписывания данных из одной ячейки в другую, с помощью которых можно достичь описанных условий. Допустимо, что относительный порядок ячеек в памяти для каждого из процессов изменится после дефрагментации, но относительный порядок самих процессов должен остаться без изменений. Это значит, что если все ячейки, принадлежащие процессу i, находились в памяти раньше всех ячеек процесса j, то и после перемещений это условие должно выполняться.

Считайте, что номера всех процессов уникальны, хотя бы одна ячейка памяти занята каким-либо процессом.


-----Входные данные-----

В первой строке входных данных записано число n (1 ≤ n ≤ 200 000) — количество ячеек в памяти компьютера.

Во второй строке входных данных следуют n целых чисел a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ n), где a_{i} равно либо 0 (это означает, что i-я ячейка памяти свободна), либо номеру процесса, которому принадлежит i-я ячейка памяти. Гарантируется, что хотя бы одно значение a_{i} не равно 0.

Процессы пронумерованы целыми числами от 1 до n в произвольном порядке. При этом процессы не обязательно пронумерованы последовательными числами.


-----Выходные данные-----

Выведите одно целое число — минимальное количество операций, которое нужно сделать для дефрагментации памяти.


-----Примеры-----
Входные данные
4
0 2 2 1

Выходные данные
2

Входные данные
8
0 8 8 8 0 4 4 2

Выходные данные
4



-----Примечание-----

В первом тестовом примере достаточно двух операций:  Переписать данные из третьей ячейки в первую. После этого память компьютера примет вид: 2 2 0 1.  Переписать данные из четвертой ячейки в третью. После этого память компьютера примет вид: 2 2 1 0.

Difficulty: MEDIUM

Starter code:

Solutions:
input()
memory = list(map(int, input().split()))
proc_data = {p: (-1, -1) for p in memory}
for (i, c) in enumerate(memory):
	(d1, d2) = proc_data[c]
	if d1 == -1:
		d1 = i
	d2 = i
	proc_data[c] = (d1, d2)
try:
	del proc_data[0]
except KeyError:
	print('0')
	return
data = list(proc_data.values())
data.sort()
ans = 0
first_free = 0
for (a, b) in data:
	c = a - first_free
	ans += min(c, b - a + 1)
	b -= c
	first_free = b + 1
print(ans)


n = int(input())
k = [[0, 0, -1]]
cnt = 0
for i in map(int, input().split()):
	if i:
		if k[-1][0] == i:
			k[-1][1] += 1
		else:
			k.append([i, 1, cnt])
	cnt += 1
cnt = 0
ans = 0
for i in k[1:]:
	ans += min(i[1], i[2] - cnt)
	cnt += i[1]
print(ans)


read = lambda : list(map(int, input().split()))
n = int(input())
a = list(read())
b = [0] * n
j = 0
for i in a:
	if i:
		b[j] = i
		j += 1
cnt = sum((i != 0 for i in b))
for i in range(n):
	if b[i] == 0:
		break
	if b[i] == a[i]:
		cnt -= 1
print(cnt)


n = int(input())
l = list(map(int, input().split()))
ans = 0
count = 0
d = dict()
s = set()
s1 = set()
for i in l:
	if i in s:
		d[i] += 1
	else:
		d[i] = 1
		s.add(i)
for i in range(n):
	if l[i] == 0:
		count += 1
	elif l[i] not in s1:
		ans += min(d[l[i]], count)
		s1.add(l[i])
print(ans)