Городские олимпиады/1-6 курсы/Межвузовская олимпиада 2016 - командный тур


1. Поломати

Ограничение по времени: 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