@Pavlin234

Как известно, знаменитые египетские пирамиды были построены инопланетянами. Именно они послужили толчком к развитию цивилизации на Земле. Но мало кто знает, что этими инопланетянами был пандорианцы. Теперь они хотят повторить свой успех на планете Макемаке.

Для постройки пирамид на Макемаке были завезены и расставлены в ряд N каменных блоков различных типов. Всего существует 9 типов блоков. Тип блока определяется его размером: самые большие блоки имеют тип 9 , а самые маленькие — 1 . Правильная пирамида должна состоять из поставленных друг на друга блоков, причем сверху обязательно должен быть блок типа 1 , а каждый блок должен стоять на блоке следующего по величине типа.

Конечно, пирамиды строят не сами пандорианцы, а местное население Макемаке. Пандорианцы лишь руководят строительным процессом, указывая, какой блок нужно двигать. Особенности анатомии макемакеанцев позволяют им поднять один блок и поставить его на первый встреченный справа блок или стопку блоков. Как только очередная пирамида оказывается достроенной (то есть на ней сверху оказывается блок типа 1 ), она вывозится из ряда блоков и устанавливается на специально подготовленную для нее площадку.

Разработайте стратегию постройки пирамид, при которой неиспользованных блоков останется как можно меньше.

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

В первой строке задано целое число N — количество завезенных блоков ( 1 ≤ N ≤ 100 000 ).

Во второй строке даны N целых чисел от 1 до 9 — типы блоков в том порядке, в котором они стоят в ряду, перечисленные слева направо.

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

Выведите минимально возможное число неиспользованных блоков.

Примечание

Во втором примере можно построить только две пирамиды высотой 1.

В третьем примере можно из стоящих в середине блоков 1 2 построить пирамиду высотой 2, а из оставшихся блоков — пирамиду высотой 5.

Тесты к этой задаче состоят из трёх групп.

Тесты 1–3. Тесты из условия, оцениваются в ноль баллов.

Тесты 4–18. В тестах этой группы 1 ≤ N ≤ 2000 . Тесты в этой группе оцениваются независимо. Каждый успешно пройденный тест оценивается в 4 балла.

Тесты 19–28. В тестах этой группы 1 ≤ N ≤ 100 000 . Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура. Тесты в этой группе оцениваются независимо. Каждый успешно пройденный тест оценивается в 4 балла.

Примеры
Входные данные

3
3 1 2

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

1

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

4
2 1 3 1

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

2

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

7
1 2 3 1 2 4 5

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

0

0

@bormant

Это задание Отборочного тура на Московскую олимпиаду по информатике для 9 классов (2018 г)
Отборочный этап проходит с 11.12.2017 по 11.02.2018 (включительно).

Пункт 4.7 Правил форума, которые вы при регистрации обещали неукоснительно выполнять, гласит:
Как можно более полно описывайте (1) суть проблемы или вопроса, (2) что было сделано для ее решения и (3) какие результаты получены.

0

@кот Бегемот

Pavlin234, забыл добавить к условию задачи: "По щучьему веленью, по моему хотенью, решите за меня олимпиадные задачи. А я чемпионом буду".

0