Задача: Дипломы в папках

В этом году Иван заканчивает школу и поступает в вуз. За время своей учебы он часто участвовал в олимпиадах по информатике и у него накопилось много дипломов. Иван раскладывал дипломы по папкам совершенно бессистемно, то есть любой диплом мог оказаться в любой из папок. К счастью, Иван помнит, сколько дипломов лежит в каждой из папок.

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

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

Входные данные
В первой строке входного файла записано целое число N (1 ≤ N ≤ 10⁵) - количество папок. Во второй строке записаны N целых чисел a₁, a₂, ..., a_N (0 ≤ a_i ≤ 10⁵) - количество дипломов в каждой из папок.

Выходные данные
Выведите одно число - минимальное количество секунд, необходимое Ивану в худшем случае для определения того, в какой папке содержится диплом.

Примечание
В первом примере Иван может открыть и просмотреть папку 2 за 2 секунды и, не найдя там диплома, понять, что диплом находится в папке 1.

Во втором примере Иван за 2 секунды просмотрит папку 1, потом за 2 секунды просмотрит папку 4, а если ни в одной из них диплома не встретилось, он поймет, что диплом в папке 3.

Примеры

Ваш ответ: