Марічка і печиво

Обмеження: 2 сек., 256 МіБ

Зібралися Зеник і Марічка разом з пластунами в похід. Похід — серйозна справа. Потрібно запастись продуктами харчування та розподілити їх споживання по днях так, щоб всім вистачило. Цього разу Зеник слідкує за тим, щоб печива вистачило аж до останнього дня походу. Зеник чітко знає, скільки пачок печива повинно залишитись кожного дня, і щовечора перераховує їх. Якщо Зеник побачить, що залишилось менше пачок, ніж повинно залишитись за його розрахунками, він неодмінно знайде того, хто з’їв забагато печива, і покарає його.

Марічка дуже любить печиво. Сьогодні, коли всі пластуни покинуть свої намети і підуть купатися в річку, Марічка планує непомітно з’їсти трохи печива. Звісно, Марічка не хоче бути покараною і дуже боїться, щоб Зеник не помітив пропажу.

Марічка підгледіла, скільки пачок печива є в рюкзаку Зеника. Також вона знає, скільки штук в кожній пачці. Марічці не терпиться дізнатися, скільки ж печива вона зможе з’їсти так, щоб Зеник не помітив. Зеник помітить пропажу печива з деякої пачки тоді і тільки тоді, коли Марічка повністю спустошить її.

Вхідні дані

У першому рядку задано одне натуральне число \(n\) — кількість пачок печива.

У другому рядку задано \(n\) натуральних чисел \(a_i\) — кількість штук печива в \(i\)-й пачці.

Вихідні дані

У єдиному рядку виведіть одне ціле число — максимальну кількість штук печива, яку зможе з’їсти Марічка так, щоб Зеник не помітив цього.

Обмеження

20% тестів:

\(1 \le n \le 1000, 0 \le a_i \le 10^4\)

60% тестів:

\(1 \le n \le 10^5, 0 \le a_i \le 10^4\)

20% тестів:

\(1 \le n \le 10^5, 0 \le a_i \le 10^9\)

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 4 7 47 74	128

Примітки

Марічка може з’їсти:

• 3 штуки печива з першої пачки

• 6 штуки печива з другої пачки

• 46 штуки печива з третьої пачки

• 73 штуки печива з четвертої пачки

• сумарно \(3+6+46+73=128\) штук печива.