Поділити гроші

Гусейн і його молодший брат знайшли на вулиці гаманець з $n$ банкнотами. Оскільки власника грошей знайти не вдалося, вони вирішили поділити гроші між собою так, щоб кожен отримав однакову суму. Після цього може залишитися найменша можлива сума, яку не вдалося поділити. Цю суму забирає Гусейн, оскільки він старший брат.

Визначте, скільки грошей дістанеться Гусейну.

Вхідні дані

Перший рядок містить ціле число $n(1\le n\le 500)$ — кількість банкнот у гаманці. Кожен з наступних $n$ рядків містить одне ціле додатне число $c_i$ — номінал $i$-ї банкноти (в манатах). Відомо, що $c_1+...+c_n\le 10^5$.

Вихідні дані

Виведіть суму грошей, яка дісталася Гусейну.

Приклади

Приклад 1. Гусейн може взяти банкноту номіналом $10$ манат, а його брат може взяти решту купюр.

Приклад 2. У початковому розподілі Гусейн може взяти банкноту номіналом $19$ манат, а його брат може взяти банкноту номіналом $17$ манат і $2$ манати. У цьому випадку банкнота номіналом $3$ манати дістається Гусейну. Таким чином, Гусейн отримає $19+3=22$ манати.