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

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

Обмеження

• \(1≤n≤2⋅10^5\)
• \(1≤t_i ​ ≤10^9\)

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

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

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

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

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

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

3
2 8 3

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

16