Єдина проста задача

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

Уявіть, що у вас є \(n\) монет, кожна з яких має вартість \(a_i\). Тепер ви робите із цим набором доволі дивні речі.

1. Розставляєте монети за принципом \(a_i \le a_{i+1}\) або \(a_i \ge a_{i + 1}\),

2. Вибираєте монети з непарними індексами.

Вам потрібно сказати, яку максимальну суму монет ви можете отримати.

Вхідні дані

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

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

Вихідні дані

У єдиному рядку виведіть ціле число — максимальну суму.

Обмеження

\(1 \le n \le 10^5\),

\(1 \le a_i \le 10^9\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
2 1 2	2

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 4 7 7	14

Примітки

Зауважте, індексація починається з 1.

У другому прикладі монети можна розставити так: 7 4 7.