Fișierul intrare/ieșire	maxp.in, maxp.out	Sursă	OJI 2013 clasa a 8-a
Autor	Dan Pracsiu	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.7 sec	Limită de memorie	32768 KB
Scorul tău	N/A	Dificultate	3

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Maxp (clasa a 8-a)

Considerăm un șir de numere a₁, a₂, ..., a_N. O secvență nevidă în acest șir este de forma a_i, a_i+1, ..., a_j, unde i ≤ j. De exemplu, pentru N=4 și șirul 2 3 4 3, secvențele nevide sunt: 2, 2 3, 2 3 4, 2 3 4 3, 3, 3 4, 3 4 3, 4, 4 3, 3. Definim puterea unui element a_i ca fiind numărul de secvențe care-l conțin pe a_i și în care a_i este strict mai mare decât celelalte elemente ale fiecăreia dintre respectivele secvențe. Astfel în șirul 2 3 4 3 puterea elementului a₁ este 1 (fiind maxim doar în secvența formată din el însuși), a elementului a₂ este 2 (a₂ fiind maxim în secvențele 2 3 și 3), a elementului a₃ este 6 (fiind maxim în secvențele 2 3 4, 2 3 4 3, 3 4, 3 4 3, 4 și 4 3), iar a elementului a₄ este 1.

Cerință

Scrieți un program care determină puterea cea mai mare a unui element din șirul dat, precum și numărul de elemente din șir care au cea mai mare putere.

Date de intrare

Fișierul maxp.in conține pe prima linie numărul natural N, iar pe a doua linie, în ordine, numerele naturale a₁, a₂, ..., a_N separate prin câte un spațiu.

Date de ieșire

Fișierul maxp.out va conține pe prima linie un număr natural ce reprezintă puterea cea mai mare a unui element din șirul dat și pe a doua linie va conține un număr natural ce reprezintă numărul de elemente din șir care au cea mai mare putere.

Restricții

• 2 ≤ N ≤ 200000
• Elementele șirului sunt numere naturale și au cel mult 6 cifre

Exemple