Školsko natjecanje iz informatike 2019. / Prva podskupina (1. i 2. razred) - 2. zadatak

Mutimir gradi stube od lego-kocaka. Njegove stube možemo prikazati kao niz stupaca od kojih svaki ima neku visinu izraženu brojem kocaka. Tako, primjerice, niz visina \((1, 3, 4, 7)\) odgovara strogo rastućim stubama s lijeva na desno, a niz visina \((8, 7, 4, 2)\) odgovara strogo padajućim stubama s lijeva na desno. S druge strane, nizovi visina \((1, 2, 1, 4)\), \((1, 2, 2, 4)\) i \((4, 2, 2, 1)\) nisu ni strogo rastući ni strogo padajući.

Mutimir želi da njegove stube budu najprije strogo rastuće, a potom strogo padajuće. Preciznije, on želi da mu stube čine niz \((a1, a2, ..., aN)\) koji je strogo rastući do svojeg najvišeg, \(K\)-tog elementa a\(K\) \((1 < K < N)\), a nakon tog elementa strogo padajući. Njegov trenutačni niz stupaca ne zadovoljava to svojstvo i Mutimir stoga mora dodati neke kocke na neke stupce.

Evo primjera: ako Mutimir trenutačno ima niz stupaca s visinama \((1, 1, 1, 1, 1)\), on može dodati po jednu kocku na \(2.\) i \(4.\) stupac te dvije kocke na \(3.\) stupac, dobivajući tako niz \((1, 2, 3, 2, 1)\) koji zadovoljava gornje svojstvo. Uvjet je moguće zadovoljiti i na druge načine, npr. dobiti niz \((1, 4, 3, 2, 1)\) ili \((1, 2, 3, 4, 1)\), no za takve stube potrebno je dodati više kocaka.

Pomozite Mutimiru i napišite program koji pronalazi najmanji ukupan broj kocaka koje treba dodati na stupce njegovog trenutačnog niza da bi dobiveni niz stuba zadovoljio opisano svojstvo „raste pa pada“.

(Obratite pažnju na sekciju Bodovanje).

Ulazni podaci

U prvom retku nalazi se prirodan broj \(N\) \((1 \leq N \leq 20)\), broj stupaca u Mutimirovom nizu.

U drugom retku nalazi se \(N\) prirodnih brojeva \(a1\), \(a2\), ..., \(aN\) \((1 \leq ai \leq 100)\) odvojeni razmakom, visine stupaca u nizu izražene brojem kocaka.

Izlazni podaci

U jedini redak ispišite traženi najmanji broj dodanih kocaka.

Bodovanje

U test podatcima vrijednima \(50\%\) bodova, broj \(N\) bit će neparan i u optimalnom rješenju najviši stupac bit će točno na sredini niza (na poziciji \((N+1)/2)\), kao u primjeru iz teksta zadatka.

Primjeri test podataka

Ulaz

5
1 1 1 1 1

Izlaz

4

Objašnjenje

Vidi tekst zadatka (dodane su ukupno četiri kocke).

Ulaz

7
3 6 5 1 9 4 7

Izlaz

13

Objašnjenje

Konačni niz je (3, 6, 7, 8, 9, 8, 7).