2068. Начало

Три – эльфийским Владыкам в подзвёздный предел;

Семь – для гномов царящих в подгорном просторе;

Девять – смертным, чей выведен срок и удел;

И Одно – Властелину на чёрном престоле.

В Мордоре, где вековечная Тьма:

Чтобы всех отыскать, воедино созвать

И единою черною волей сковать

В Мордоре, где вековечная Tьма.

   Джон Р. Р. Толкин Властелин колец

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

Всего ему нужно раздать `m` колец. Они все разделены на `n` групп – эльфийские, гномьи и так далее. В `i`-й группе `a_i` колец. Саурон выбирает какую-то группу колец и раздает их. Однако, перед этим нужно огласить на весь зал имя получателя кольца со всеми его регалиями. Так как для получения колец выбирались самые достойные представители, список регалий может быть очень длинным, а Саурону хочется закончить с нагаждением. Поэтому он решил, что когда все кольца, которые ему осталось раздать, будут из одной группы, он сможет отдать их все сразу без оглашения списка. Помогите ему выяснить, какое наименьшее число имён ему всё-таки придётся зачитать.

В первой строке задано число `n` (`1\ ≤\ n≤\ 1000`) – количество групп. Во второй строке задано `n` чисел `a_i` (`1\ ≤\ a_i\ ≤\ 1000`) – численности групп.

Выведите единственное число – минимальное число имён, которое придётся зачитать Саурону.

4
3 7 9 1

11