Є n мішків монет, пронумерованих від 1 до n. На кожному мішку написано число монет, що знаходяться у ньому. Один з мішків наповнено виключно фальшивими монетами. У інших мішках всі монети - справжні.

Справжня монета важить 10 грамів, фальшива - 9 грамів. Є веги, які показують загальну вагу покладених на неї монет. Потрібно визначити найменшу кількість зважувань, які знадоюляться, для того щоб встановити, у якому мішку фальшиві монети, при абсолютному невезінні. Для цього з кожного мішка можна брати скільки завгодно багато монет. Крім того, монети можна мітити номером мішка, з якого вони були взяті.

Вхідні дані

У першому рядку записано одне число n (1 ≤ n ≤ 30000) - кількість мішків. Починаючи з наступного рядка, записано n чисел, що відповідають кількості монет у відповідному мішку. Ці числа знаходяться в діапазоні від 1 до 100000.

Вихідні дані

Вивести одне число - мінімальну кількість зважувань.