---
title: Konfektes
---

Pie apaļa galda sēž pāra skaits bērnu. Katram bērnam ir kaut kāds skaits konfekšu. Varēja gadīties, ka konfektes tika sadalītas negodīgi: godīgā sadalījumā katram bērnam būtu tikpat daudz konfekšu, cik tam bērnam, kurš sēž viņam galda pretējā pusē.

Jūsu uzdevums ir atrast mazāko gājienu skaitu, kas nepieciešams, lai nonāktu līdz godīgam sadalījumam. Vienā gājienā kāds bērns var iedot vienu no savām konfektēm blakusesošam bērnam. Katram $1 \le i \le n-1$ bērni ar numuriem $i$ un $i+1$ ir blakusesoši, kā arī bērni $n$ un $1$ arī ir blakusesoši. Katram $1 \le i \le \frac{n}{2}$, bērni ar numuriem $i$ un $i+\frac{n}{2}$ sēž pretējās pusēs galdam.

# Ievaddati

Pirmajā rindiņā ir viens vesels skaitlis $n$: bērnu skaits ap galdu. Ir garantēts, ka $n$ ir pāra skaitlis.

Otrā rindiņa satur $n$ veselus skaitļus $c_1, c_2, \ldots, c_n$: konfekšu skaits, ar kuru sāk katrs bērns. 

# Izvaddati

Izvadiet mazāko gājienu skaitu. Ja nav iespējams iegūt godīgu sadalījumu, izvadiet "`IMPOSSIBLE`".

# Ierobežojumi

- $2 \le n \le 10^5$
- $0 \le c_k \le 10^9$

# Piemērs 1

Ievaddati:

```
8
4 5 1 7 0 0 3 4
```

Izvaddati:

```
12
```

_Paskaidrojums_: Bērns $2$ iedod četras konfektes bērnam $3$ un vienu konfekti bērnam $1$. Tad bērns $1$ iedod visas piecas konfektes bērnam $8$ un bērns $3$ iedod divas konfektes bērnam $4$. Pēc visiem gājieniem konfekšu sadalījums ir `0 0 3 9 0 0 3 9`.

# Piemērs 2

Ievaddati:

```
6
1 2 3 1 1 1
```

Izvaddati:

```
IMPOSSIBLE
```

# Vērtēšana

| Apakšuzdevums | Ierobežojumi | Punkti    |
| :-----: | ----------- | :-------: |
| 1       | $n \le 4$, $c_1 + c_2 + \dots + c_n \le 4$ | [score=1] |
| 2       | Visiem bērniem izņemot bērnu $1$ ir nulle konfekšu | [score=2] |
| 3       | Bez papildu ierobežojumiem | [score=3] |
