Hannah's Brain - Repovive Starter Round 2 | Repovive

10C. Hannah's Brain

1500 pts1s256 MB

Hannah has $n$ CPUs. The $i$ -th CPU initially has $a_i$ cores.

In one operation, she chooses one CPU with $x$ cores and splits it into two CPUs with positive integer numbers of cores $y$ and $x-y$ , where $1 \le y < x$ .

After performing some number of operations, Hannah wants all remaining CPUs to have the same number of cores.

Find the minimum number of operations required.

Constraints

$1 \le n \le 5\,000$
$1 \le a_i \le 5\,000$

Input

$n$

$a_1 \quad a_2 \quad \ldots \quad a_n$

Output

$\text{ans}$

Samples

Input

2
2 6

Explanation

First, split the CPU with 6 cores into two CPUs with 4 and 2 cores. Then split the CPU with 4 cores into two CPUs with 2 and 2 cores.

Output

Input

3
3 3 3

Explanation

All CPUs already have the same number of cores; no splits are needed.

Output

Hannah has $n$ CPUs. The $i$ -th CPU initially has $a_i$ cores.

In one operation, she chooses one CPU with $x$ cores and splits it into two CPUs with positive integer numbers of cores $y$ and $x-y$ , where $1 \le y < x$ .

After performing some number of operations, Hannah wants all remaining CPUs to have the same number of cores.

Find the minimum number of operations required.

$1 \le n \le 5\,000$
$1 \le a_i \le 5\,000$

$n$

$a_1 \quad a_2 \quad \ldots \quad a_n$

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

10C. Hannah's Brain

Constraints

Input

Output

Samples

10C. Hannah's Brain

Constraints

Input

Output

Samples