ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1742. Тим-билдинг

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В компании, занимающейся разработкой программного обеспечения, работают n программистов. Каждый из них считает себя либо первым, либо вторым по силе программистом в компании. Во втором случае он может назвать коллегу, который, по его мнению, является более сильным программистом.
Руководство компании решило поделить всех программистов на группы разработки, действуя по следующему алгоритму:
  1. Если есть программисты, ещё не определённые ни в одну из групп разработки, выбираем любого из них и называем его текущим.
  2. Создаётся новая группа разработки, куда направляется текущий программист.
  3. Если текущий программист считает кого-то из коллег более сильным и этот программист ещё не определён ни в одну группу разработки, то он направляется в эту же группу, после чего сам объявляется текущим. Затем шаг 3 повторяется. Иначе формирование группы на этом заканчивается, и руководство возвращается к шагу 1.
Какое минимальное и максимальное количество групп разработки можно сформировать в этой компании, действуя по описанному алгоритму?

Исходные данные

В первой строке записано целое число n (1 ≤ n ≤ 105). В i-й из следующих n строк указан номер программиста, которого i-й программист считает самым сильным в компании.

Результат

Выведите через пробел минимальное и максимальное количество групп разработки.

Пример

исходные данныерезультат
4
2
3
4
2
1 2
Автор задачи: Артём Рипатти
Источник задачи: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009