Владимир Борисович работает руководителем в одной очень крупной компании. В его служебные обязанности в числе прочего входит рассмотрение и согласование заявок, которые отправляют сотрудники через специальную информационную систему. Владимир Борисович согласовывает заявки разных типов: всего имеется $$$n$$$ типов заявок. Он зашёл в приложение для согласования заявок и увидел, что там имеется $$$a_1$$$ заявок первого типа, $$$a_2$$$ второго и т.д.
Процесс согласования выглядит следующим образом: заявки отмечаются галочкой, и нажимается кнопка «Согласовать». Кнопка работает только тогда, когда все отмеченные заявки имеют один и тот же тип, то есть нельзя одновременно согласовать несколько заявок разных типов. Согласованные заявки исчезают из списка заявок. Нажатием на кнопку-галочку возле заявки можно не только отметить её, но и снять отметку. Есть ещё кнопка «Отметить все», которая выставляет галочки напротив всех заявок в отмеченное положение.
За какое наименьшее количество нажатий кнопок в приложении Владимир Борисович может согласовать все заявки?
В первой строке входных данных записано число $$$n$$$ — количество типов заявок ($$$1 \leq n \leq 10^5$$$). В следующих $$$n$$$ строках записано по одному числу: $$$a_1, a_2, a_3$$$ и так далее — количество поступивших заявок каждого типа ($$$1 \leq a_i \leq 10^4$$$ для всех $$$i$$$).
В результате работы программы требуется вывести единственное число — минимальное возможное количество нажатий кнопок для согласования всех заявок.
Решения, правильно работающие при дополнительном ограничении $$$n \leq 1000$$$, будут набирать не менее 70 баллов.
232
5
3111
6
Решения, правильно работающие при дополнительном ограничении $$$n \leq 1000$$$, будут набирать не менее 70 баллов.
Пояснение к примеру
В первом примере выгоднее всего отметить сначала две заявки второго типа и нажать кнопку «Согласовать», потратив на это суммарно три нажатия на кнопки, после этого нажать кнопку «Отметить все» и затем кнопку «Согласовать», потратив ещё два нажатия, и таким образом согласовать все заявки, используя пять нажатий кнопок. Нетрудно проверить, что любые другие способы согласования требуют большего количества нажатий.
