---
title: Saldainiai
---

Lyginis skaičius vaikų sėdi prie apskrito stalo. Kiekvienas vaikas turi tam tikrą skaičių saldainių. Deja, saldainiai gali būti padalinti nesąžiningai: sąžiningame padalinime kiekvienas vaikas turi lygiai tokį patį saldainių skaičių kaip ir priešingoje stalo pusėje sėdintis vaikas.

Jums reikia surasti mažiausią ėjimų skaičių reikalingą gauti sąžiningą saldainių padalinimą. Vieno ėjimo metu vienas vaikas gali duoti vieną jo saldainių šalia sėdinčiam vaikui. Visiems $1 \le i \le n-1$, vaikai $i$ ir $i+1$ sėdi šalia, bei vaikai $n$ ir $1$ taip pat sėdi šalia. Kiekvienam $1 \le i \le \frac{n}{2}$, vaikai $i$ ir $i+\frac{n}{2}$ sėdi priešingose stalo pusėse.

# Pradiniai duomenys

Pirmoje eilutėje pateiktas lyginis sveikasis skaičius $n$ – vaikų, sėdinčių prie apskrito stalo, skaičius.

Antroje eilutėje pateikta $n$ sveikųjų skaičių $c_1, c_2, \ldots, c_n$ – kiekvieno vaiko pradinis saldainių skaičius.

# Išvestis

Išveskite mažiausią reikalingą ėjimų skaičių. Jei saldainių perskirstyti sąžiningai neįmanoma, išveskite "`IMPOSSIBLE`".

# Ribojimai

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

# Pavyzdys 1

Pradiniai duomenys:

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

Išvestis:

```
12
```

_Paaiškinimas_: Vaikas $2$ duoda keturis saldainius vaikui $3$ ir vieną saldainį vaikui $1$. Tada vaikas $1$ duoda visus penkis savo saldainius vaikui $8$, o vaikas $3$ duoda du saldainius vaikui $4$. Po visų ėjimų saldainių išsidėstymas yra `0 0 3 9 0 0 3 9`.

# Pavyzdys 2

Pradiniai duomenys:

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

Išvestis:

```
IMPOSSIBLE
```

# Vertinimas

| Dalinė užduotis | Ribojimai | Taškai    |
| :-----: | ----------- | :-------: |
| 1       | $n \le 4$, $c_1 + c_2 + \dots + c_n \le 4$ | [score=1] |
| 2       | Visi vaikai išskyrus vaiką $1$ turi nulį saldainių | [score=2] |
| 3       | Papildomų ribojimų nėra | [score=3] |
