#OJ1795. 程序

程序

程序

Time Limit: 3 Sec  Memory Limit: 128 MB

Description

哆啦A梦很喜欢写代码。在缩代码方面,他是一位身经百战的老手。世界各地的OJ上,很多题的最短解答排行榜都有他的身影。这令他感到十分愉悦。 

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

现在设哆啦A梦有一份 n 行的代码,第 i 行有 ai 个空格作为缩进。

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

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

Input

多组数据,对于每一组数据


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


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


n<=10^6,ai<=10^6

Output

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

Sample Input

3
5
8
8

Sample Output

6

HINT

Append Code