eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Мешок фальшивых денег

Мешок фальшивых денег

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Имеется n мешков монет, пронумерованных от 1 до n. На каждом мешке написано число лежащих в нем монет. Один мешок наполнен только фальшивыми монетами. В остальных мешках все монеты - настоящие.

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

Входные данные

В первой строке записано одно число n - количество мешков (1n30000). Начиная со следующей строки, записано n чисел, обозначающих число монет в соответствующем мешке. Эти числа находятся в диапазоне от 1 до 100000.

Выходные данные

Вывести одно число - минимальное количество взвешиваний.

Пример

Входные данные #1
3
5 10 2
Выходные данные #1
1