Zid

Un monument istoric are forma unui zid circular format din $N$ turnuri. Fiecare turn este construit din cărămizi zidite unele peste altele. Înălțimea unui turn este egală cu numărul de cărămizi din care este format turnul.

Zidul trebuie renovat astfel încât, după renovare, turnurile din zid să aibă aceeași înălțime.

Înălțimea finală a zidului renovat trebuie să fie cât mai mică.
Pentru renovare se va utiliza o mașină care, la o comandă, alege două turnuri vecine și adaugă în cele două turnuri alese același număr de cărămizi.

În situația în care problema nu are soluție, vor trebui eliminate din zid un număr minim de cărămizi, astfel încât, după eliminare, renovarea să fie posibilă.

Cerință

Dacă problema nu are soluție, determinați nrmin, numărul minim de cărămizi care trebuie eliminate astfel încât, după eliminare, renovarea să poată avea loc.
Dacă problema are soluție, determinați hmin, înălțimea finală minimă după renovare.

Date de intrare

Fișierul de intrare zid.in conține pe prima linie numărul $N$. Pe a doua linie sunt scrise $N$ numere naturale $h_1 h_2 \cdots h_N$ separate prin câte un spațiu, reprezentând înălțimile inițiale ale turnurilor, în ordine de la $1$ la $N$.

Date de ieșire

În fișierul de ieșire zid.out se va scrie pe primul rând unul dintre numerele nrmin sau hmin, după caz.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$
• $0 \leq h_k \leq 1 \ 000 \ 000,\, 1 \leq k \leq N$
• Se garantează că răspunsul este cel mult egal cu $10^9$.

Exemplul 1

zid.in

4
1 2 4 3

zid.out

4

Explicație

Pentru exemplul $1$, se pot aplica următoarele comenzi:

• la pozițiile $1$ și $2$ se zidesc câte $2$ cărămizi și se obține zidul $3$ $4$ $4$ $3$;
• la pozițiile $1$ și $4$ se zidește câte o cărămidă și se obține zidul $4$ $4$ $4$ $4$.

Exemplul 2

zid.in

2
1 3

zid.out

2

Explicație

Exemplul $2$ nu se poate rezolva decât dacă se vor elimina $2$ cărămizi din turnul $2$.

Exemplul 3

zid.in

5
5 2 1 3 4

zid.out

5

Explicație

Pentru exemplul $3$, se pot aplica următoarele comenzi:

• la pozițiile $3$ și $4$ se zidește câte o cărămidă și se obține zidul $5$ $2$ $2$ $4$ $4$;
• la pozițiile $2$ și $3$ se zidesc câte trei cărămizi și se obține zidul $5$ $5$ $5$ $4$ $4$;
• la pozițiile $4$ și $5$ se zidește câte o cărămidă și se obține zidul $5$ $5$ $5$ $5$ $5$.