---
title: Karkit
---

Parillinen määrä lapsia istuu pyöreän pöydän ympärillä. Jokaisella lapsella on jokin määrä karkkeja. Kuitenkin karkit saattavat olla jakautuneet epäreilusti: reilussa jakaumassa jokaisella lapsella on sama määrä karkkeja kuin vastakkaisella puolella pöytää istuvalla lapsella.

Tehtäväsi on etsiä pienin määrä siirtoja, joilla saavutetaan reilu jakauma. Yksi siirto tarkoittaa, että yksi lapsi antaa yhden karkeistaan viereiselle lapselle. Lapset $i$ ja $i+1$ ovat toistensa vieressä, kun $1 \le i \le n-1$, ja lisäksi lapset $n$ ja $1$ ovat toistensa vieressä. Lapset $i$ ja $i+\frac{n}{2}$ istuvat pöydän vastakkaisilla puolilla, kun $1 \le i \le \frac{n}{2}$.

# Syöte

Ensimmäisellä rivillä on parillinen kokonaisluku $n$: pöydän ympärillä olevien lasten määrä.

Toisella rivillä on $n$ kokonaislukua $c_1, c_2, \ldots, c_n$: jokaisen lapsen karkkien määrä alussa.

# Tuloste

Tulosta pienin siirtomäärä. Jos reilua jakaumaa ei voi saavuttaa, tulosta "`IMPOSSIBLE`".

# Rajat

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

# Esimerkki 1

Syöte:

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

Tuloste:

```
12
```

_Selitys_: Lapsi $2$ antaa neljä karkkia lapselle $3$ ja yhden karkin lapselle $1$. Sitten lapsi $1$ antaa kaikki viisi karkkiaan lapselle $8$ ja lapsi $3$ antaa kaksi karkkia lapselle $4$. Näiden siirtojen jälkeen karkkien jakauma on  `0 0 3 9 0 0 3 9`.

# Esimerkki 2

Syöte:

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

Tuloste:

```
IMPOSSIBLE
```

# Pisteytys

| Osatehtävä | Rajoitukset | Pisteet    |
| :-----: | ----------- | :-------: |
| 1       | $n \le 4$, $c_1 + c_2 + \dots + c_n \le 4$ | [score=1] |
| 2       | Vain lapsella $1$ on yli nolla karkkia | [score=2] |
| 3       | Ei lisärajoituksia | [score=3] |
