babilon

Babilonienii au dezvoltat un sistem pozițional de scriere a numerelor, în care orice număr natural se poate reprezenta utilizând semnele:

Valorile $k$ din {$2$, $3$, $...$, $9$} se obțin scriind semnul pentru unu de $k$ ori
Exemplu: scrierea babiloniană a lui $3$ este
Figura 3 din enunțul original al problemei babilon.Mărește schema ↗

Numerele $11$, $12$, $\dots$, $59$ se obțin ca succesiuni de semne urmate de semne
Exemplu: $43$ se reprezintă ca
Figura 4 din enunțul original al problemei babilon.Mărește schema ↗
Sistemul folosește gruparea unităților câte șaizeci. Astfel, pentru a scrie numărul șaizeci se folosește același semn ca pentru unu, dar valoarea sa este dată de poziția în care se găsește semnul.
Babilonienii nu foloseau cifra $0$. Pentru poziţionarea corectă a semnelor se utiliza spațiu:
Figura 5 din enunțul original al problemei babilon.Mărește schema ↗

Exemple:

Se codifică scrierea babiloniană a unui număr astfel:

Exemple:

Cerință

Dându-se un număr natural $n$ și un șir de $n$ cifre dintre {$1$, $2$, $3$}, reprezentând codificarea scrierii babiloniene a unui număr natural, să se determine:

1. numărul maxim de cifre $1$ aflate pe poziții consecutive în codificarea scrierii babiloniene date;
2. numărul natural din sistemul zecimal corespunzător scrierii babiloniene date.

Date de intrare

Fișierul de intrare babilon.in va conține:

• pe prima linie un număr natural $p$ ($1 \leq p \leq 2$);
• pe a doua linie un număr natural $n$;
• pe a treia linie $n$ cifre separate prin câte un spațiu, reprezentând codificarea scrierii babiloniene a unui număr natural.

Date de ieșire

Dacă valoarea lui $p$ este $1$, atunci se va rezolva numai punctul $1$ din cerință. În acest caz, fişierul de ieşire babilon.out va conţine pe prima linie un număr natural reprezentând numărul maxim de cifre $1$ aflate pe poziții consecutive în codificarea scrierii babiloniene date.
Dacă valoarea lui $p$ este $2$, atunci se va rezolva numai punctul $2$ din cerință. În acest caz, fişierul de ieşire babilon.out va conţine pe prima linie numărul natural corespunzător scrierii babiloniene date.

Restricţii şi precizări

• $2 \leq n \leq 109$;
• se garantează faptul că numărul de cifre al rezultatului de la punctul $2$ (numărul zecimal) este mai mic decât $20$;
• $30\%$ din teste vor avea pe prima linie valoarea $1$, iar restul de $70\%$ din teste vor avea pe prima linie valoarea $2$.

Exemplul 1

babilon.in

1
8
1 1 3 2 1 1 1 2

babilon.out

3

Explicație

$1 \ 1 \ 3 \ 2$ 1 1 1 $2$
Cea mai lungă secvență de cifre $1$ are lungimea $3$.

Exemplul 2

babilon.in

2
7
1 1 3 2 1 1 1

babilon.out

7213

Explicație

Figura 15 din enunțul original al problemei babilon.Mărește schema ↗
$2$ se înmulțește de două ori cu $60$ (o dată pentru că este urmat de spațiu și încă o dată pentru că precede o grupă care începe cu semnul pentru zece), apoi se adună valoarea $13$.
$2 \cdot 60 \cdot 60 + 10 + 3 = 7213$

Exemplul 3

babilon.in

2
9
1 1 1 2 1 1 2 2 1

babilon.out

11541

Explicație

Figura 16 din enunțul original al problemei babilon.Mărește schema ↗
$3$ se înmulțește cu $60$ de două ori pentru că este precedat de două grupe care încep cu semnul pentru zece, apoi se adună $12$ înmulţit cu $60$ şi la final se adună $21$.
$3 \cdot 60 \cdot 60 + 12 \cdot 60 + 21 = 11541$