题目背景

有一位刚学OI的蒟蒻，一次发现自己的行数比另外一份代码少，但是总长度比它长。比对后发现他的代码中的缩进都是空格！于是他准备用Tab来代替空格。

题目描述

他原来的代码一共有\(n\)行，第\(i\)(\(1≤i≤n\))行的缩进空格数是\(a_i\)。用Tab代替空格时，假设Tab的长度是\(x\)，对于第每一行，把每连续\(x\)个空格替换成一个Tab，直到剩余空格数不足\(x\)个。在每一份代码中，Tab的长度不可变换。替换后本行的长度为Tab的个数加上空格的个数。他想让他的代码尽量短。你的任务是选择一个合适的\(x\)，使得这个代码最短，输出这个最短的代码有多长。

输入格式

\(n\)
\(a_1\) \(a_2\) \(a_3\) ... \(a_n\)

输出格式

最短代码的长度。

输入输出样例

输入

3
5 8 8

输出

6

样例解释

令Tab的长度为4就能得到长度为6的最短代码。

数据范围

对于\(20\%\)的数据，\(n≤1,000\)，\(a_i≤2,000\)。
对于\(40\%\)的数据，\(n≤100,000\)，\(a_i≤2,000\)。
对于\(70\%\)的数据，\(n,a_i≤100,000\)。
对于\(100\%\)的数据，\(1≤n,a_i≤1,000,000\)。

贡献者

题面：b6e0。
数据：b6e0。