Today, Sema and Yura attended the closing ceremony of one Olympiad. On the holiday tables there were n plates of nuts. The i-th plate contains ai nuts.

In one minute Sema can choose some plates and a certain number x, after which from each selected plate he picks up exactly x nuts (of course, each selected plate should have at least x nuts).

Determine in what minimum number of minutes all the nuts will be in Sema's pocket.

Input

The first line contains one integer n (1 ≤ n ≤ 50) - the number of plates with nuts.

Second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 50) - the number of the nuts in the i-th plate.

Output

Print a single number - the required minimum number of minutes.