Віллі Вонка володіє шоколадною фабрикою, яка виробляє безліч різних соладощів. Інколи Віллі Вонка роздає солодощі безкоштовно. Перед фабрикою вишиковується довжелезний ряд дітвори і кожному що-небудь вручають.
Скоро настане черговий з таких досить рідких випадків. Цього разу було вирішено роздавати цукерки. Фабрика виробляє N різних видів цукерок. Віллі Вонка збирається віддати кожному з дітей набір з N-1 штук різних цукерок. Біда лише у тому, що кількості цукерок різних видів можуть відрізнятись, і стає важко підрахувати, скільком дітям дістанеться подарунок при такій схемі у найкращомму випадку. Ось це вам і доведеться зробити.
Перший рядок містить число N (2 ≤ N ≤ 10000) – кількість різних видів цукерок.
Кожен i-ий з наступних N рядків містить одне число – кількість цукерок i-ого типу. Кількість цукерок одного типу буде у діапазоні від 1 до 500000000, включно.
Єдине число – максимальна кількість комплектів з N-1 цукерок, які можна отримати, якщо розподіляти цукерки оптимально.