Задача №112102. Макемакеанские пирамиды (CD)
Как известно, знаменитые египетские пирамиды были построены инопланетянами. Именно они послужили толчком к развитию цивилизации на Земле. Но мало кто знает, что этими инопланетянами был пандорианцы. Теперь они хотят повторить свой успех на планете Макемаке.
Для постройки пирамид на Макемаке были завезены и расставлены в ряд 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