Богиня Те Фити благосклонна к людям, но периодически проверяет использование ее ресурсов и просит у вождя Туи отчет.
Как только на небе показывается звезда Мотунуи, Туи обязан оставить на берегу океана бумажку с показателем успешности работы племени над природными ресурсами. Чем выше показатель работы, тем более благосклонна будет богиня в дальнейшем, и более плодородными будут земли острова.
Испокон веков этот показатель рассчитывается так: у вождя есть количество кокосов $$$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$$$ — максимально возможный показатель успешности за период.
108 5 9 6 6 5 8 7 9 6
19
В данном примере оптимально выбрать $$$t = 5$$$.