ruleta

Nicușor este elev în clasa a VI-a și s-a gândit că este suficient de mare ca să inventeze un joc nou. Are doar o foaie de hârtie și un pix. Scrie mai întâi $n$ numere naturale în cerc. Acestea formează Ruleta numerelor. Jocul se desfășoară după următoarele reguli:

• se parcurge șirul numerelor în sensul deplasării acelor de ceasornic;
• se pornește de fiecare dată de la același element;
• se execută de fiecare dată o rotație completă;
• fiecare element nenul se scade din elementul imediat următor doar dacă este mai mic sau egal cu acesta și nenul;

Exemplu. Dacă notăm cu $R_1, R_2, R_3, R_4, R_5, R_6, R_7, R8$ șirul numerelor ce formează ruleta din figura $1$, atunci, o rotație completă realizează următoarele modificări asupra numerelor din listă:

• ruleta se oprește atunci când execută o rotație completă și nu se modifică nici o valoare din șirul elementelor.

Exemplu. Pentru ruleta din figura $1$ se execută $4$ rotații (dintre care $3$ în care se fac modificări):

Cerință

Scrieți un program care să determine, pentru un șir de $n$ numere naturale care indică starea inițială a ruletei, numărul $r$ de rotații complete efectuate respectând regulile jocului până la încheierea acestuia și numărul $t$ al elementelor nenule aflate în șir la încheierea jocului.

Date de intrare

Fișierul de intrare ruleta.in conține pe prima linie numărul $n$ de numere naturale așezate în cerc iar pe linia a doua, separate prin câte un spațiu, cele $n$ valori, în ordinea deplasării, începând cu elementul de la care pornește ruleta.

Date de ieșire

Fișierul de ieșire ruleta.out conține pe prima linie, separate printr-un spațiu, valorile $r$ și $t$ (în această ordine).

Restricții și precizări

• $2 \leq n \leq 10 \ 000$;
• Numerele de pe ruletă sunt numere naturale mai mici sau cel mult egale cu $30 \ 000$.
• pentru aflarea corectă a numărului $r$ de rotaţii se acordă 70% din punctajul pe test; punctajul integral se acordă dacă ambele valori afişate sunt corecte.

Exemplu

ruleta.in

8
1 2 3 4 3 2 3 1

ruleta.out

4 3