Optimal Currency Design for Purchasing Rabbits

Little Snake, the Finance Minister, is designing a new series of coin denominations. The coin system is defined by a sequence \(x_1, x_2, x_3, \dots\) that must satisfy the following conditions:

• \(x_1 = 1\).
• For any two indices with \(b > a\), the coin \(x_b\) is a positive integer multiple of \(x_a\), i.e. \(x_b = k \cdot x_a\) for some positive integer \(k\). For example, the sequence \(1, 5, 125, 250\) is legal, but \(1, 5, 100, 125\) is not.

Enamored by cute rabbits, Little Snake wishes to purchase \(N\) rabbits whose prices are given by \(a_1, a_2, \dots, a_N\). When buying a rabbit, she must pay the exact amount without receiving change. She can use an unlimited supply of each coin.

One can show that an optimal legal coin sequence is a geometric progression: namely, choosing a base \(r \ge 1\) so that the coins become \(1, r, r^2, r^3, \dots\). When \(r = 1\), every coin has value 1 and the number of coins needed to pay \(a_i\) is simply \(a_i\). When \(r > 1\), note that representing \(a_i\) in base \(r\) yields a unique expansion \(a_i = d_k r^k + d_{k-1} r^{k-1} + \cdots + d_0\) and the number of coins used is \(d_k + d_{k-1} + \cdots + d_0\).

Your task is to choose an integer \(r \ge 1\) (which determines the legal coin sequence) so that the total number of coins required to exactly pay for all \(N\) rabbits is minimized. Output the minimum total number of coins required.

inputFormat

The first line contains a single integer \(N\) (the number of rabbits). The second line contains \(N\) space-separated positive integers \(a_1, a_2, \dots, a_N\) representing the prices of the rabbits.

outputFormat

Output a single integer: the minimum total number of coins needed to purchase all the rabbits under an optimal legal coin sequence.

sample

3
2 8 9

4