235

Definim o putere a lui $3$ un număr de forma $3^k$, ($k$ număr natural strict pozitiv), o putere a lui $5$ un număr de forma $5^k$ (k număr natural strict pozitiv), iar o putere a lui $2$ un număr de forma $2^k$ ($k$ număr natural strict pozitiv).
Se dă un șir de $n$ numere naturale. Plecând de la acest șir, formăm un nou șir prin eliminarea tuturor numerele care nu sunt puteri ale lui $3$ și nici puteri ale lui $5$. Ordinea relativă între numerele care nu sunt eliminate se păstrează.

Cerințe

• Să se determine câte numere conține șirul nou format.
• Să se determine de asemenea numărul de secvențe având lungimea egală cu o putere a lui $2$ existente în șirul nou format în care numărul de puteri ale lui $3$ este egal cu numărul de puteri ale lui $5$. O secvență este formată din elemente aflate pe poziții consecutive în acest șir nou format, iar lungimea unei secvențe este egală cu numărul de elemente pe care aceasta îl conține.

Date de intrare

Pe prima linie in fișierul 235.in se afla un număr natural $n$. Pe fiecare dintre următoarele $n$ linii câte un număr natural mai mare decât $1$ reprezentând numerele șirului inițial.

Date de ieșire

Pe prima linie a fișierului 235.out se va afla o valoare naturală $m$ care va reprezenta numărul de elemente rămase în șir după eliminare. Pe a doua linie se va afla o valoare naturală $S$ reprezentând numărul de secvențe din șirul nou format care au proprietățile cerute.

Restricții și precizări

• $2 \leq n \leq 500 \ 000$;
• Numerele din șirul inițial sunt numere naturale din intervalul [$2, 2 \cdot 10^9$].
• Se garantează că $m \leq 40 \ 000$; pentru fiecare set de date de intrare.
• Pentru determinarea corectă a valorii numărului $m$ se acordă $30$% din punctaj iar pentru determinarea corectă a ambelor valori ($m$ şi $s$) se acordă $100$% din punctaj.

Exemplu

235.in

8
625
125
5
9
15
81
100
125

235.out

6
4

Explicație

Șirul rămas după eliminarea numerelor care nu sunt puteri ale lui $5$ sau ale lui $3$ are $6$ elemente: $625, 125, 5, 9, 81, 125$.

În acest șir sunt:

• două secvențe formate din două valori care conțin un număr egal de puteri ale lui $3$ și ale lui $5$: $5, 9$ și $81, 125$;
• două secvențe de patru numere care conțin un număr egal de puteri ale lui $3$ și ale lui $5$: $125, 5, 9, 81$ și $5, 9, 81, 125$