Отчетность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Богиня Те Фити благосклонна к людям, но периодически проверяет использование ее ресурсов и просит у вождя Туи отчет.

Как только на небе показывается звезда Мотунуи, Туи обязан оставить на берегу океана бумажку с показателем успешности работы племени над природными ресурсами. Чем выше показатель работы, тем более благосклонна будет богиня в дальнейшем, и более плодородными будут земли острова.

Испокон веков этот показатель рассчитывается так: у вождя есть количество кокосов $$$a_i$$$, собранное соплеменниками за каждый из $$$n$$$ дней промежутка времени, тогда успешность использования ресурсов равна $$$$$$P = \sum\limits_{i = 1}^{n} (a_i \bmod t)$$$$$$ для некоторого $$$t \le \min(a)$$$.

Очевидно, что вождю выгодно максимизировать $$$P$$$ для увеличения благосклонности богини, при этом $$$t$$$ он может выбрать сам. Помогите ему определить оптимальное значение $$$t$$$ для отчета и соответствующий ему показатель $$$P$$$.

Входные данные

В первой строке ввода дано целое положительное число $$$n$$$ — количество дней в периоде отчета ($$$1 \le n \le 2 \cdot 10^5$$$).

Во второй строке перечислены $$$n$$$ чисел $$$a_i$$$ — количество кокосов, собранных в $$$i$$$-й день ($$$1 \le a_i \le 2 \cdot 10^5$$$).

Выходные данные

Выведите одно число $$$P$$$ — максимально возможный показатель успешности за период.

Пример

Входные данные
10
8 5 9 6 6 5 8 7 9 6
Выходные данные
19

Примечание

В данном примере оптимально выбрать $$$t = 5$$$.