Имеется n мешков монет, пронумерованных от 1 до n. На каждом мешке написано число лежащих в нем монет. Один мешок наполнен только фальшивыми монетами. В остальных мешках все монеты - настоящие.
Настоящая монета весит 10 граммов, фальшивая - 9 граммов. Имеются весы, которые показывают общий вес положенных на них монет. Требуется определить наименьшее число взвешиваний, которые потребуются, для того чтобы установить, в каком мешке фальшивые монеты, при абсолютном невезении. Для этого из каждого мешка можно брать сколь угодно много монет. Кроме того, монеты можно помечать номером мешка, из которого они были взяты.
В первой строке записано одно число n - количество мешков (1 ≤ n ≤ 30000). Начиная со следующей строки, записано n чисел, обозначающих число монет в соответствующем мешке. Эти числа находятся в диапазоне от 1 до 100000.
Вывести одно число - минимальное количество взвешиваний.