Description:


小O是一个热爱短代码的选手。在缩代码方面,他是一位身经百战的老手。世界各地的OJ上,很多题的最短解答排行榜都有他的身影。这令他感到十分愉悦。

最近,他突然发现,很多时候自己的程序明明看起来比别人的更短,实际代码量却更长。这令他感到很费解。经过一番研究,原来是因为他每一行的缩进都全是由空格组成的,大量的空格让代码量随之增大。

现在设小O有一份 n 行的代码,第 i 行有 ai 个空格作为缩进。

为解决这一问题,小O要给自己文本编辑器设定一个正整数的默认TAB宽度 x,然后对于每一行,编辑器从头至尾不断把连续 x 个空格替换成一个TAB,直到剩余空格数不足 x 个。

最终缩进所占代码量为空格数与TAB数的和。请你帮小O选择一个合适的 x,使得缩进所占代码量最小。

Input:


第一行一个正整数 n,表示代码行数。

接下来 n 行,第 i 行一个正整数 ai,为初始时第 i 行缩进的空格个数。

Output:


一行一个整数,表示缩进所占代码量最小是多少。

C/C++ 输入输出 long long 时请用 %lld。C++ 可以直接使用 cin/cout 输入输出。

Input:


3
5
8
8

Output:


题解:


一开始想三分,后来发现不是单峰的。

其实UOJ的题解很详细了,我们要最大化节约的代码: \((x-1)\sum_{i=1}^n \lfloor frac{a_i}{x} \rfloor \) .

然后可以枚举 \(x\) ,再枚举

,统计区间 \([t\times x, (t+1)\times x -1 ]\) 有多少个 \(a_i\)

时间复杂度 \(O(n\ln n)\)