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

Електронна пошта

Електронна пошта

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Користувач мережі Інтернет підписаний на декілька різних списків розсилки, які висилають йому по електроній пошті повідомлення на певні теми. Для зручності користувач створив собі набір папок, кожна з яких відповідає одній з тем. Перед тим, як читати повідомлення він копіює їх у відповідну папку.

Поштова програма, встановлена на комп'ютері користувача, дозволяє за одну "операцію" переносити зі "списку нових повідомлень" у відповідну папку:

  • Одне повідомлення з довільного місця списку

  • Декілька повідомлень, які йдуть у списку підряд, і відносяться до однієї теми

Переносити можна не обов'язковно починаючи з початку "списку нових повідомлень". Користувачу необхідно перенести усі нові повідомлення у відповідні їм папки за найменшу кількість операцій.

Приклад. Нехай користувач підписаний на розсилки анекдотів, веселих історій, спортивних новин та прогноз погоди. Нехай "список нових повідомлень" при деякому входженні у поштову програму мав наступний вигляд: (Анекдоти, Спортивні новини, Прогноз погоди, Спортивні новини, Веселі історії, Веселі історії, Спортивні новини)

Переносити повідомлення у папки він може наступним чином: спочатку два повідомлення на тему "Веселі історії". Тоді він отрмає наступний список: (Анекдоти, Спортивні новини, Прогноз погоди, Спортивні новини, Спортивні новини). Потім перенести повідомлення про прогноз погоди, після цього "Анекдоти", а потім, одночасно, усі три повідомлення про спортивні новини. На це він витратить 4 "операції".

Напишіть програму, яка буде обчислювати мінімальну кількість "операцій", при допомозі яких можна перенести усі нові повідомлення у папки. Для зручності кожній темі присвоюється номер.

Вхідні дані

Єдиний рядок містить кількість нових повідомлень N (0 < N < 200) та N цілих чисел, які відповідають повідомленням, і є номерами тем, яким ці повідомлення належать.

Вихідні дані

Вивести мінімальну кількість операцій для даних, наведених у вході.

Приклад

Вхідні дані #1
7 1 3 4 3 2 2 3
Вихідні дані #1
4
Джерело 2000 XIII Всеукраїнська олімпіада з інформатики, Київ, Березень 27 - Квітень 1, тур 2