Память компьютера состоит из 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: interview

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
    else:
        if l[i] not in s1:
            ans += min(d[l[i]], count)
            s1.add(l[i])
print(ans)