maxp

Considerăm un șir de numere $a_1, a_2, \dots, a_N$. O secvență nevidă în acest șir este de forma $a_i, a_{i+1}, \dots, a_j$, unde $i \leq 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_1$ este $1$ (fiind maxim doar în secvența formată din el însuși), a elementului $a_2$ este $2$ ($a_2$ fiind maxim în secvențele $2 \ 3$ și $3$), a elementului $a_3$ 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_4$ 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_1, a_2, \dots, 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 și precizări

• $2 \leq N \leq 200 \ 000$;
• Elementele șirului sunt numere naturale și au cel mult $6$ cifre
• Se acordă 50% din punctaj pentru determinarea corectă a celei mai mari puteri a unui element din șir și 50% din punctaj pentru determinarea numărului de elemente din şir care au cea mai mare putere.

Exemplul 1

maxp.in

7
9 3 4 5 1 2 2

maxp.out

12
1

Explicație

Elementul $5$ de pe poziția $4$ este maxim în $12$ secvențe:

$3 \ 4 \ 5, 3 \ 4 \ 5 \ 1, 3 \ 4 \ 5 \ 1 \ 2, 3 \ 4 \ 5 \ 1 \ 2 \ 2, 4 \ 5, 4 \ 5 \ 1, 4 \ 5 \ 1 \ 2, 4 \ 5 \ 1 \ 2 \ 2, 5, 5 \ 1, 5 \ 1 \ 2, 5 \ 1 \ 2 \ 2$, deci puterea lui este $12$. Este singurul element care are această putere, celelalte elemente având puteri mai mici.

Exemplul 2

maxp.in

6
1 0 7 7 2 6

maxp.out

3
2

Explicație

Elementele din pozițiile $3$ și $4$ sunt maxime în $3$ secvențe, deci puterea lor este $3$. Celelalte elemente au puteri mai mici.