butoane

Echipa SG1 se află în fața unei noi provocări. Un dispozitiv antic are un sistem foarte ciudat prin care poate fi pus în funcțiune. Dispozitivul are $n$ butoane numerotate de la stânga la dreapta de la $1$ la $n$. Pe fiecare buton se găsește un număr natural. Suma tuturor numerelor de pe butoane este divizibilă cu $n$.

S-a constatat că la atingerea butoanelor din capete (butonul $1$ și butonul $n$) numărul scris pe acestea scade cu o unitate, iar numărul de pe butonul vecin crește cu o unitate. Dacă se atinge unul dintre celelalte butoane (cele numerotate cu $2, 3, \dots, n-1$) numărul corespunzător scade cu două unități, iar cele corespunzătoare vecinilor cresc cu câte o unitate. Dispozitivul va fi pus în funcțiune dacă toate cele $n$ numere devin egale.

Ajuțati echipa SG1 să pună dispozitivul în funcțiune folosind un număr minim de atingeri ale butoanelor.

Date de intrare

Fișierul de intrare butoane.in conține pe prima linie numărul natural $n$, reprezentând numărul de butoane. Pe cea de-a doua linie se află $n$ numere naturale, separate prin câte un spațiu, reprezentând în ordine valorile înscrise inițial pe cele $n$ butoane.

Date de ieșire

Fișierul de ieșire butoane.out va conține $n$ linii. Pe linia $i$ ($1 \leq i \leq n$) se va afișa un număr natural reprezentând numărul de atingeri ale butonului $i$.

Restricții și precizări

• $3 \leq n \leq 1 \ 000$
• Numerele înscrise inițial pe cele n butoane sunt numere naturale mai mici sau egale cu $100$. Suma celor $n$ numere este divizibilă cu $n$.
• Numărul de atingeri ale oricărui buton va fi $\leq 2 \ 000 \ 000 \ 000$ (două miliarde).
• Punctaj. Dacă programul afișează o soluție care determină deschiderea dispozitivului cu număr minim de atingeri, obține integral punctajul pentru testul respectiv. Dacă numărul de atingeri nu este minim, dar soluția afișată determină deschiderea dispozitivului, se obține $30\%$ din punctaj.

Exemplu

butoane.in

3
10 11 12

butoane.out

0
1
2