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

Limits: 2 sec., 256 MiB

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

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

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

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

Input

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

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

Output

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

Constraints

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

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

Samples

Input (stdin) сopy	Output (stdout) сopy
2 1 2	2

Input (stdin) сopy	Output (stdout) сopy
3 4 7 7	14

Notes

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

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