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