Definim o putere a lui 3 un număr de forma 3k, (k număr natural strict pozitiv), o putere a lui 5 un număr de forma 5k (k număr natural strict pozitiv), iar o putere a lui 2 un număr de forma 2k (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ţă
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
2 ≤ n ≤ 500000
Numerele din şirul iniţial sunt numere naturale din intervalul [2,2000000000].
Se garantează că m ≤ 40000 pentru fiecare set de date de intrare.
Exemple
235.in
235.out
Explicaţii
8
625
125
5
9
15
81
100
125
6
4
Ş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