Региональная олимпиада по программированию среди студентов 1-6 курсов 2016. Командный тур.

Соревнование завершилось 14.05.16 в 17:30

A. Поломати

Ограничение по времени: 1 с.
Ограничение по памяти: 64 МБ

Как-то раз Соловей-Разбойник забрался через форточку в дом к Алёше Поповичу — поглядеть, как живут богатыри русские, да добром поживиться, конечно же. Видит разбойник стены каменные, шкафы деревянные, а в центре гостиной сейфы стальные стоят — ровно N штук, да все под замками кодовыми.

Но Соловей и сам-то не лыком шит — накануне прикупил он у фарцовщицы Яги N кодовых ключей, с гарантией даже — уверяет Яга, что каждый ключ точно подходит к какому-нибудь сейфу из дома Алеши Поповича. Только вот беда — не понятно к какому сейфу подходит какой ключ. Благо Соловей давно взломом промышляет и уже знает оптимальную (как кажется ему самому) стратегию подбора ключей. Осталось посчитать сколько попыток подбора потребуется в худшем случае, чтобы для каждого ключа найти сейф, который он открывает.

А действует Соловей следующим образом: берет ключ наиболее популярного вида, пробует им открыть все закрытые сейфы. После успеха, выкидывает и ключ и открытый сейф. Затем берет следующий ключ наиболее популярного вида и повторяет эти действия и так далее, пока все сейфы не откроются.

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

В первой строке входных данных дано целое число N — количество сейфов и в то же время ключей (1 ≤ N ≤ 105).

Затем во второй строке задано N целых чисел Ai — значения кодовых ключей (1 ≤ Ai ≤ 105, где 1 ≤ iN).

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

В единственной строке необходимо вывести единственное целое число — количество попыток подбора ключа к сейфу в худшем случае при оптимальной стратегии.

Примеры
Стандартный вводСтандартный вывод
7
1 1 1 1 2 2 3
21
7
1 2 3 4 5 6 7
28

Для вывода 64-битных целых оператором printf в C необходимо использовать спецификатор %lld.


В задаче A "Поломати", как выяснилось :(, Соловей-Разбойник не всегда действует оптимально. Он действует следующим образом. Берет ключ наиболее популярного вида, пробует им открыть все закрытые сейфы. После успеха, выкидывает и ключ и открытый сейф. Затем берет следующий ключ наиболее популярного вида и повторяет эти действия и так далее. Простите нас, пожалуйста :(


В задаче C "Тракт": Если гонец выезжает на тракт в момент, когда в точке его въезда находится колесница, то он уступает ей. Другими словами, гонец остается позади.


В задаче C "Тракт": Гонцы в любой момент времени движутся равномерно (с постоянной скоростью). Если они догоняют троицу, то они так же движутся равномерно со скоростью троицы.


В задаче C "Тракт": богатыри не могут двигаться с бесконечно большой скоростью, то есть они не могут преодолеть ненулевую дистанцию за нулевое время.


В задаче A "Поломати" условие следует понимать так: "Соловей-Разбойник после того, как открыл сейф, выбрасывает ключ и убирает открытый сейф. Все закрытые сейфы для него снова неотличимы - он забывает, какие сейфы он уже пробовал открыть и какими ключами".