The Birthday Party

Little Kasia is throwing a birthday party. For the occasion she bought $n$ different kinds of candy; there are $x_k$ candies of the $k$-th kind.

Kasia hands the candy out to the guests she invites. For each kind, every guest must receive the same number of candies, and candies cannot be broken into pieces. When more than one amount per guest is possible, she always picks the largest one. For example, with $10$ candies and $4$ guests she could give each person $0$, $1$, or $2$ candies, so she gives the maximum, $2$ each. Thus if there are $m$ guests, every guest receives $\lfloor x_k / m \rfloor$ candies of the $k$-th kind and Kasia keeps $x_k \bmod m$ of them.

Kasia has not tasted any of the candy yet, so she wants at least one candy of every kind to remain for herself after the sharing. In other words, for every $k$ the remainder of $x_k$ divided by $m$ must be at least $1$. Kasia is not very sociable, so find the smallest number of guests $m$ she must invite to satisfy this condition.

The first line contains an integer $n$, the number of candy kinds ($1 \le n \le 10^6$).

The second line contains $n$ integers $x_k$, separated by spaces, where $x_k$ is the number of candies of the $k$-th kind ($1 \le x_k \le 10^5$).

Print a single integer: the smallest number of guests Kasia must invite.