Є ~n~ книжок, і Віка та Юля збираються прочитати їх усі. Для кожної книги ви знаєте час, який потрібно для її прочитання. Вони обоє читають кожну книгу від початку до кінця, і вони не можуть читати книгу одночасно.

Який мінімальний загальний час необхідний?

Обмеження

• ~1≤n≤2⋅10^5~
• ~1≤t_i≤10^9~

Формат вхідних даних

У першому рядку вхідних даних є ціле число ~n~: кількість книг.

У другому рядку є ~n~ цілих чисел ~t_1 ​,t_2 ​ ,…,t_n~ ​ : час, необхідний для читання кожної книги.

Формат вихідних даних

Вивести одне ціле число: мінімальний загальний час.

Приклад вхідних даних

3
2 8 3

Приклад вихідних даних

16