Tartibga solish

O‘qituvchi Komila Sobirovna sinfda ketma-ket joylashgan $n$ ta partaga ega. Agar o‘quvchi $i$-partaga o‘tirsa, o‘qituvchining mamnunligi $p[i]$ ga o‘zgaradi.

Sinfda aniq $\lceil \frac{n}{2} \rceil$ ta o‘quvchi bor. Komila Sobirovna barcha o‘quvchilarni shunday partalarga o‘tqazishi kerakki, hech qanday ikki o‘quvchi qo‘shni partalarda o‘tirmasin. Barcha yaroqli joylashtirishlar orasidan umumiy mamnunlikni maksimal qiladiganini toping.

\textit{Eslatma:} $\lceil x \rceil$ $x$ dan katta yoki unga teng bo‘lgan eng kichik butun sonni bildiradi. Masalan, $\lceil 3.14 \rceil = 4$ va $\lceil 5 \rceil = 5$.

### Kiritish formati

Birinchi qatorda $n$ --- partalar soni beriladi.

Ikkinchi qatorda $n$ ta butun son $p[1], p[2], \ldots, p[n]$ --- har bir partaning o‘qituvchi mamnunligiga ta’siri beriladi.

Cheklovlar:

$1 \leq n \leq 10^5$

$-10^9 \leq p[i] \leq 10^9$, har bir $1 \leq i \leq n$ uchun

### Chiqish formati

Bitta qatorda o‘qituvchi olishi mumkin bo‘lgan maksimal mamnunlikni chiqaring.

### Baholash

{|c|c|c|}

\hline

**Subtask** & **Cheklov** & **Ballar**

\hline

1 & $n$ toq & 10

\hline

2 & $n \leq 5$ & 10

\hline

3 & $n \leq 1000$ & 35

\hline

4 & Qo‘shimcha cheklovlar yo‘q & 45

\hline

### Izohlar

**Birinchi namunada**, $n=6$ va $\lceil \frac{6}{2} \rceil = 3$ ta o‘quvchi. Komila Sobirovna ularni $1$, $4$ va $6$-partalarga o‘tqazadi. Umumiy mamnunlik: $p[1]+p[4]+p[6] = 5+3+7 = 15$.

**Ikkinchi namunada**, $n=3$ va $\lceil \frac{3}{2} \rceil = 2$ ta o‘quvchi. Yagona variant $1$ va $3$-partalar. Umumiy mamnunlik: $p[1]+p[3] = (-1)+(-3) = -4$.