Расположение

Учительница Комила Собировна имеет $n$ парт в классе, расположенных в ряд. Когда ученик садится за парту $i$, удовольствие учительницы изменяется на $p[i]$.

В классе ровно $\lceil \frac{n}{2} \rceil$ учеников. Комиле Собировне нужно рассадить всех учеников за парты так, чтобы никакие два ученика не сидели за соседними партами. Среди всех допустимых рассадок найдите ту, которая максимизирует суммарное удовольствие.

\textit{Примечание:} $\lceil x \rceil$ обозначает наименьшее целое число, большее или равное $x$. Например, $\lceil 3.14 \rceil = 4$ и $\lceil 5 \rceil = 5$.

### Формат ввода

Первая строка содержит целое число $n$ --- количество парт.

Вторая строка содержит $n$ целых чисел $p[1], p[2], \ldots, p[n]$ --- влияние каждой парты на удовольствие учительницы.

Ограничения:

$1 \leq n \leq 10^5$

$-10^9 \leq p[i] \leq 10^9$, для каждого $1 \leq i \leq n$

### Формат вывода

В одной строке выведите максимальное удовольствие, которое может получить учительница.

### Оценивание

{|c|c|c|}

\hline

**Подзадача** & **Ограничение** & **Баллы**

\hline

1 & $n$ нечётно & 10

\hline

2 & $n \leq 5$ & 10

\hline

3 & $n \leq 1000$ & 35

\hline

4 & Без дополнительных ограничений & 45

\hline

### Примечания

В **первом примере**, $n=6$ и $\lceil \frac{6}{2} \rceil = 3$ ученика. Комила Собировна рассаживает их за парты $1$, $4$ и $6$. Суммарное удовольствие: $p[1]+p[4]+p[6] = 5+3+7 = 15$.

Во **втором примере**, $n=3$ и $\lceil \frac{3}{2} \rceil = 2$ ученика. Единственный вариант — парты $1$ и $3$. Суммарное удовольствие: $p[1]+p[3] = (-1)+(-3) = -4$.