Макемакеанские пирамиды

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

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

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

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

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

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

Пример 1
Ввод
3
3 1 2
Вывод
1

Пример 2
Ввод
4
2 1 3 1
Вывод
2

Пример 3
Ввод
7
1 2 3 1 2 4 5
Вывод
0

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

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

0