UOJ Logo Universal Online Judge

UOJ

#21. 【UR #1】缩进优化

统计

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

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

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

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

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

输入格式

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

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

输出格式

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

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

样例一

input

3
5
8
8

output

6

explanation

令默认TAB宽度为4即可。

样例二

input

10
2
3
5
7
11
13
17
19
23
29

output

45

样例三

见样例数据下载

限制与约定

测试点编号 $n$的规模 $a_i$的大小
1$n \leq 10^3$$a_i \leq 2000$
2
3$n \leq 10^5$$a_i \leq 2000$
4
5$n \leq 10^5$$a_i \leq 10^5$
6
7
8$n \leq 10^6$$a_i \leq 10^6$
9
10

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载