eolymp
Competitions

XIII Всеукраинская олимпиада по информатике, Киев, Март 27 - Апрель 1, 2000

Электронная почта

Пользователь сети Интернет подписан на несколько разных списков рассылки, которые высылают ему по электронной почте сообщения на определенные темы. Для удобства пользователь создал себе набор папок, каждая из которых соответствует одной из тем. Перед тем, как читать сообщения он копирует их в соответствующую папку.

Почтовая программа, установленная на компьютере пользователя, позволяет за одну "операцию" переносить из "списка новых сообщений" в соответствующую папку:

  • Одно сообщение из любого места списка
  • Несколько сообщений, идущих в списке подряд, и относящихся к одной теме

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

Пример. Пусть пользователь подписан на рассылки анекдотов, веселых историй, спортивных новостей и прогноза погоды. Пусть "список новых сообщений" при некотором вхождении в почтовую программу имел следующий вид: (Анекдоты, Спортивные новости, Прогноз погоды, Спортивные новости, Веселые истории, Веселые истории, Спортивные новости)

Список папок

Список новых сообщений

1

Анекдоты

1

Анекдоты

2

Веселые истории

3

Спортивные новости

3

Спортивные новости

4

Прогноз погоды

4

Прогноз погоды

3

Спортивные новости

2

Веселые истории

2

Веселые истории

3

Спортивные новости

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

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

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

Одна строка содержит количество новых сообщений N (0 < N < 200) и N целых чисел, которые соответствуют сообщениям, и являются номерами тем, которым эти сообщения принадлежат.

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

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

Time limit 1 second
Memory limit 64 MiB
Input example #1
7 1 3 4 3 2 2 3
Output example #1
4
Source 2000 XIII All-Ukrainian Informatics Olympiad, Kiev, March 27 - April 1, Round 2