Pracsiu Dan (dnprx) Harap Alb, mergând înfricoșat prin pădure spre Împăratul Roșu, se întâlnește cu un Spân. Acesta din urmă se oferă să îl însoțească pe fiul de Crai în călătoria sa, dar Harap trebuie să îi ofere în schimb rezolvarea unei probleme de natură algoritmică. Harap Alb neștiind Informatică, dar vrând, totuși, să fie însoțit de Spân, vă roagă să îl ajutați cu rezolvarea următoarei probleme:
Dându-se un șir A de N numere naturale nenule numerotate de la 1 la N, să se determine câte subsecvențe [L,R] cu 1 < L ≤ R < N există, astfel încât elementele A[L], A[L+1], ..., A[R] să fie strict mai mari decât elementele A[L-1] și A[R+1]. De asemenea, se cere și determinarea lungimii maxime a unei astfel de secvențe. În imaginea de mai jos sunt reprezentate secvențele corespunzătoare primului exemplu:
Cerința
Scrieți un program care să rezolve următoarele două cerințe:
1) Să se determine lungimea maximă a unei subsecvențe ce respectă proprietatea din enunț;
2) Să se determine numărul de subsecvențe ce respectă proprietatea din enunț.
Date de intrare
Fișierul de intrare harapalb.in conține pe prima linie numărul natural C, reprezentând cerința care trebuie să fie rezolvată, respectiv numărul natural N, reprezentând dimensiunea șirului. Pe a doua linie a fișierului se vor afla N numere naturale, reprezentând numerele din șirul A. Valorile scrise pe aceeași linie sunt separate prin câte un spațiu.
Date de ieșire
Fișierul de ieșire harapalb.out va conține o singură linie pe care va fi scris răspunsul la cerința din fișierul de intrare.
Restricții și precizări
3 ≤ N ≤ 1.000.0000 ≤ A[i] ≤ 1.000.000pentru oriceiîntre1șiN
Exemplul 1:
harapalb.in
1 12 0 1 2 4 3 1 3 4 5 2 1 0
harapalb.out
10
Explicație
Exemplul este ilustrat în fotografie. Se observă că lungimea maximă a unei subsecvențe ce respectă proprietatea din enunț este 10 și sunt 8 astfel de subsecvențe.
Exemplul 2:
harapalb.in
2 12 0 1 2 4 3 1 3 4 5 2 1 0
harapalb.out
8
Exemplul 3:
harapalb.in
1 12 0 1 2 4 4 1 0 2 4 1 0 0
harapalb.out
5
Exemplul 4:
harapalb.in
2 12 0 1 2 4 4 1 0 2 4 1 0 0
harapalb.out
6