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