Матрёшкой называют набор традиционных русских деревянных кукол уменьшающегося размера, помещенных внутрь друг друга. Матрёшку можно открыть, чтобы достать изнутри меньшую матрёшку, у которой, в свою очередь, внутри также есть матрёшка и так далее.
В Национальном Матрёшечном музее недавно проходила выставка матрёшек, на которой были представлены похожие по стилю, но отличающиеся количеством матрёшек в наборе куклы. С сожалению, один шаловливый (и оставленный без присмотра) ребенок разобрал все матрёшки и выставил все куклы в ряд.
В ряду оказалось n матрешек, про каждую известен ее целочисленный размер. Вам нужно заново собрать все матрешки в наборы, однако вы не знаете ни изначальное количество наборов, ни количество кукол в каждом из наборов. Вы знаете только то, что каждый набор состоит из кукол всех последовательных размеров от 1 до некоторого m, причем m может быть различным для различных наборов.
При сборке наборов нужно руководствоваться следующими правилами:
можно поместить матрешку только внутрь матрешку большего размера;
можно объединить две матрешки только если они стоят рядом в ряду;
после того как матрешку помещают внутрь набора матрешек, ее нельзя переместить в другую группу матрешек или отделить от группы матрешек. Разрешается только временно разделить ее при объединении двух групп матрешек.
Ваше время очень ценно, поэтому вы хотите собрать все матрешки в группы как можно быстрее. Единственная часть процесса, которая занимает время, это открытие и после этого закрытие куклы, поэтому вы хотите минимизировать количество именно таких действий. Например, минимальное количество действий для объединения группы [1,2,6] и [4] — два, сначала нужно открыть матрешки размеров 6 и 4. Объединение групп [1,2,5] и [3,4] требует трех открытий.
Напишите программу, которая вычислит минимальное количество открытий, необходимых для сборки всех наборов матрешек.
Вам дан один тест, состоящий из двух строк. Первая строка содержит одно число n (1 ≤ n ≤ 500) - количество отдельных кукол в изначальном ряду. Во второй строке находится n чисел, описывающих размер каждой куклы в ряду. Размер каждой куклы не менее 1 и не превосходит 500.
Выведите минимальное количество открытий матрешек, необходимое для того, чтобы собрать все наборы. Если сборка невозможна (ребенок мог забрать несколько кукол себе), выведите слово impossible.