eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Матрёшка

Матрёшка

Лимит времени 5 секунд
Лимит использования памяти 256 MiB

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

В Национальном Матрёшечном музее недавно проходила выставка матрёшек, на которой были представлены похожие по стилю, но отличающиеся количеством матрёшек в наборе куклы. С сожалению, один шаловливый (и оставленный без присмотра) ребенок разобрал все матрёшки и выставил все куклы в ряд.

В ряду оказалось n матрешек, про каждую известен ее целочисленный размер. Вам нужно заново собрать все матрешки в наборы, однако вы не знаете ни изначальное количество наборов, ни количество кукол в каждом из наборов. Вы знаете только то, что каждый набор состоит из кукол всех последовательных размеров от 1 до некоторого m, причем m может быть различным для различных наборов.

При сборке наборов нужно руководствоваться следующими правилами:

  • можно поместить матрешку только внутрь матрешку большего размера;

  • можно объединить две матрешки только если они стоят рядом в ряду;

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

Ваше время очень ценно, поэтому вы хотите собрать все матрешки в группы как можно быстрее. Единственная часть процесса, которая занимает время, это открытие и после этого закрытие куклы, поэтому вы хотите минимизировать количество именно таких действий. Например, минимальное количество действий для объединения группы [1,2,6] и [4] — два, сначала нужно открыть матрешки размеров 6 и 4. Объединение групп [1,2,5] и [3,4] требует трех открытий.

Напишите программу, которая вычислит минимальное количество открытий, необходимых для сборки всех наборов матрешек.

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

Вам дан один тест, состоящий из двух строк. Первая строка содержит одно число n (1n500) - количество отдельных кукол в изначальном ряду. Во второй строке находится n чисел, описывающих размер каждой куклы в ряду. Размер каждой куклы не менее 1 и не превосходит 500.

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

Выведите минимальное количество открытий матрешек, необходимое для того, чтобы собрать все наборы. Если сборка невозможна (ребенок мог забрать несколько кукол себе), выведите слово impossible.

Пример

Входные данные #1
7
1 2 3 2 4 1 3
Выходные данные #1
7
Источник ACM-ICPC World Finals 2013