There are n bags of coins, numbered from 1 to n. The number of coins lying in a bag is written on each bag. One bag is filled only with fake coins. In other bags the coins are real.

The weight of the normal coin is 10 gram, the weight of the fake coin is 9 gram. There are scales that show the total weight of the coins placed on them. You must determine the least number of weighings required to determine in what bag fake coins, with an absolute bad luck. You can take any number of coins from any bag. In addition, the coins can be marked with bag number, from which they were taken.

Input

The first line contains the number of bags n (1 ≤ n ≤ 30000). Beginning from the next line, n numbers are written - the number of coins in each bag. These numbers are in the range from 1 to 100000.

Output

Print the minimum possible number of weighings.