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

Обмеження: 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.