Матрьошка
Матрьошки - це традиційні русійські дерев'яні ляльки, вкладені одна в одну за зменшенням розміру. Матрьошку можна відкрити і дістати з неї іншу матрьошку, яка у свою чергу може містити в собі ще одну і так далі.
У російському музеї матрьошок нещодавно демонструвались колекції матрьошек однакового дизайну, які відрізнялись між собою лише кількістю ляльок всередині кожної колекції. На жаль, знайшлись знадто допитливі дітки (що залишились без догляду батьків), які разібрали усі матрьошки і розставили їх в ряд. У ряду розміщено n ляльок, кожна з яких має цілочисельний розмір. Вам необхідно зібрати набори матрьошок, не знаючи ні кількості наборів, ні числа матрьошок у кожному з них. Відомо лише те, що кожен з наборів складається з матрьошок з послідовними розмірами від 1 до деякого значення m, яке може змінюватись від набору до набору.
Під час збірки Вам потрібно дотримуватись наступних правил:
Ви можете покласти матрьошку чи групу матрьошек лише всередину більшої матрьошки.
Дві групи матрьошек можна об'єднати, лише якщо вони стоять поряд у ряду.
Коли лялька стає членом групи, її вже неможоиво перенести у іншу групу чи назавжди відокремити від групи. Її можна лише тимчасово відокремити під час злиття двох груп.
Час це гроші, тому збірку потрібно здійснити якомогашвидше. Єдиною операцією, яка вимгає затрат часу у цій задачі, є відкриття та відповідно закриття матрьошки, тому Ви хочете мінімізувати їх кількість. Наприклад, найменшу кількість операцій відкриття (і відповідно операцій закривання) при комбінуванні груп [1, 2, 6] та [4] дорівнює двом, так як достатньо відкрити лише матрьошки з розмірами 6 та 4. При об'єднанні груп [1, 2, 5] та [3, 4] достатньо трьох відкривань.
Напишіть програму, яка знайде найменшу кількість відкривань, достатніх для збірки усіх множин матрьошок.
Вхідні дані
Вхідні дані складаються з одного тесту. Тест складається з двох рядків. Перший рядок містить одне ціле числоn (1 ≤ n ≤ 500) - кількість матрьошок, що стоять окремо у ряду. Другий рядок містить n натуральних чисел - розміри матрьошок у тому ж порядку, у якому вони розміщені у ряду. Розміри матрьошок змінюються від 1 до 500 включно.
Вихідні дані
Вивести найменшу кількість операцій відкривання, необхідних для збірки наборів матрьошок. Якщо збірка неможлива (діти були занадто допитливими і забрали з собою деякі матрьошки), то вивести слово impossible.