Саша играет в новую игру «Vanjurs Fate» и сейчас готовится к битве с финальным боссом Ванжуром. У Саши есть N героев. Обычно он прокачивает всех своих героев до предела и перед битвой с боссом собирает их вместе, чтобы не оставлять боссу шансов. Сейчас все герои Саши прокачиваются в N разных локациях, причём в каждой локации ровно один герой. Саша распределил героев так, чтобы набрать им как можно больше опыта, но теперь у него проблемы со сбором всех героев в локации с Ванжуром. Сейчас ни один из героев не находится в локации с боссом.

Саша знает, что i-му герою требуется ровно d_i секунд, чтобы самостоятельно добраться до локации с боссом Ванжуром. Ещё Саша, пока прокачивал героев, нашёл легендарную книгу. Её может мгновенно прочитать любой из героев, после чего книга уничтожится. Герой, прочитавший книгу, навсегда получит навык массовой телепортации. Он сможет за 1 секунду телепортировать себя и всех героев, находящихся с ним в одной локации, в любую точку любой другой локации. Причём этот навык можно использовать сколько угодно раз.

Саша хочет за минимальное время собрать всех героев в локации с боссом. Он может приказать каждому герою без навыка либо самому за d_i секунд добраться до локации с боссом, либо ждать появления героя с навыком телепортации и после его появления путешествовать с ним. Герою с навыком массовой телепортации Саша может выбрать любой маршрут по локациям, главное, чтобы он тоже в конце оказался в локации с боссом. Все герои начнут выполнять приказы одновременно. Помогите Саше и найдите минимальное время, за которое можно собрать всех героев в локации с Ванжуром.

Первая строка содержит одно целое число N — количество героев (1 ≤ N ≤ 10⁵).

Вторая строка содержит N целых чисел d_i — время в секундах, за которое i-й герой самостоятельно добирается до локации с боссом (1 ≤ d_i ≤ 10⁹).

Выведите одно целое число — минимальное время, за которое Саша соберёт всех героев в локации с боссом.

В первом наборе входных данных Саша может дать книгу второму герою и сказать ему телепортироваться сразу к боссу. Тогда первый и второй герои придут к боссу за 1 секунду, а третий герой — за 2 секунды.

Во втором наборе книгу можно отдать третьему герою и сказать ему забрать первого, четвёртого и шестого героев. Тогда они вместе телепортируются к локации босса за 4 секунды. Второй и пятый герои придут к локации босса самостоятельно за 4 секунды, а седьмой герой — за 1 секунду. То есть все герои через 4 секунды прибудут к Ванжуру.