---
title: Kommid
---

Paarisarv lapsi istuvad ümara laua ümber. Igal lapsel on mingi arv komme. Kuid kommid võivad olla jagatud ebaõiglaselt: õiglase jaotuse korral on igal lapsel sama palju komme kui üle laua tema vastas istuval lapsel.

Sinu ülesandeks on leida minimaalne arv käike, mida on vaja, et jõuda õiglase jaotuseni. Ühe käiguga saab üks laps anda ühe oma kommidest kõrval olevale lapsele. Iga $1 \le i \le n-1$ korral on lapsed numbritega $i$ ja $i+1$ kõrvuti, ning lapsed numbritega $n$ ja $1$ on samuti kõrvuti. Iga $1 \le i \le \frac{n}{2}$ korral istuvad lapsed numbritega $i$ ja $i+\frac{n}{2}$ üle laua üksteise vastas.

# Sisend

Esimesel real on paaris täisarv $n$: laua ümber olevate laste arv.

Teisel real on $n$ täisarvu, $c_1, c_2, \ldots, c_n$: Iga lapse algne kommide arv.

# Väljund

Väljasta minimaalne võimalik käikude arv, et saavutada õiglane jaotus. Kui õiglase jaotuse saavutamine on võimatu, siis väljasta "`IMPOSSIBLE`".

# Piirangud

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

# Näide 1

Sisend:

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

Väljund:

```
12
```

_Selgitus_: Laps $2$ annab neli kommi lapsele $3$ ja ühe kommi lapsele $1$. Siis annab laps $1$ kõik oma viis kommi lapsele $8$, ja laps $3$ annab kaks kommi lapsele $4$. Pärast käike on kommide jaotus `0 0 3 9 0 0 3 9`.

# Näide 2

Sisend:

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

Väljund:

```
IMPOSSIBLE
```

# Hindamine

| Grupp | Piirangud | Punktid    |
| :-----: | ----------- | :-------: |
| 1       | $n \le 4$, $c_1 + c_2 + \dots + c_n \le 4$ | [score=1] |
| 2       | Kõigil lastel peale lapse $1$ on alguses null kommi | [score=2] |
| 3       | Lisapiirangud puuduvad | [score=3] |
