muntele Alinei

Cerință

Alina este o elevă în clasa a 6-a pasionată de matematică. Într-o zi a scos din dulapul ei câteva cartonașe, iar pe fiecare din ele a notat câte un număr natural de maxim $3$ cifre și apoi le-a aranjat pe biroul ei unul lângă altul. La un moment dat s-a apucat să mute un singur cartonaș de pe masă la începutul șirului astfel încât lipind cartonașele după această mutare să obțină cel mai mare număr posibil. Abia a terminat această operațiune că a intrat pe ușă fratele ei Cristian (pasionat de geografie) care i-a propus Alinei să găsească în șirul ei de cartonașe cea mai lungă secvență munte.

O secvență de numere este o succesiune de elemente numerice care apar pe poziții consecutive, cum ar fi secvența $(30, 40, 50)$ din șirul $(10, 20, 30, 40, 50, 60, 70, 80)$.

Se consideră un şir $x_1, x_2, \ldots, x_n$ format din $n$ numere naturale distincte. O secvenţă de număr maxim de elemente vecine în şir, de forma $x_i, x_{i+1}, \ldots, x_{k-1}, x_k, x_{k+1}, \ldots, x_j (1 \leq i \lt k \lt j \leq n)$ cu proprietatea că $x_i < x_{i+1} < \ldots < x_{k-1} < x_k > x_{k+1} > \ldots > x_j$, se numeşte munte cu vârful $x_k$. O secvenţă munte are cel puţin $3$ elemente. Un exemplu de şir format cu valorile $3$ $4$ $6$ $8$ nu conţine nicio secvenţă munte, iar unul format cu valorile $3$ $4$ $8$ $1$ $2$ $5$ $0$ conţine $2$ secvenţe munte: $3$ $4$ $8$ $1$ şi $1$ $2$ $5$ $0$.

Date de intrare

Fișierul de intrare muntele-alinei.in conține pe prima linie numerele naturale $c$ și $n$, iar pe a 2-a linie cele $n$ numerele naturale din șir separate prin câte un spaţiu.

Date de ieșire

Fișierul de ieșire muntele-alinei.out va conține pe prima linie un număr natural:

• dacă $c=1$ numărul respectiv va fi cel obținut după mutarea a maxim un număr din șirul inițial pe prima poziție și apoi lipirea în ordine a numerelor șir.
• dacă $c=2$ numărul obținut va fi lungimea celei mai mari secvențe munte după mutarea a maxim un număr din șirul inițial (dacă nu există nicio secvență munte în șirul respectiv se va afișa valoarea $0$).

Restricții și precizări

• $c \leq 2$;
• $3 \leq n \leq 1000$;
• Mutarea se va face obligatoriu în cazul în care prin aceasta se poate obține un număr mai mare decât cel din șirul inițial, în caz contrar nu se efectuează vreo mutare.
• Fiecare număr din șir are maxim $3$ cifre;
• pentru teste în valoare de $20$ de puncte $c=1$ și se garantează că fiecare număr din șir are o singură cifră;
• pentru teste în valoare de inca $40$ de puncte $c=1$;
• pentru teste în valoare de $40$ de puncte $c=2$.

Exemplul 1

muntele-alinei.in

1
5
345 20 87 14 63

muntele-alinei.out

87345201463

Explicație

După mutarea numărului $87$ la începutul șirului obținem șirul $87$ $345$ $20$ $14$ $63$.

Exemplul 2

muntele-alinei.in

2
5
345 20 87 14 63

muntele-alinei.out

4

Explicație

După mutarea numărului $87$ la începutul șirului obținem șirul $87$ $345$ $20$ $14$ $63$.

Exemplul 3

muntele-alinei.in

2
5
8 7 9 3 2  

muntele-alinei.out

0

Explicație

După mutarea numărului $9$ la începutul șirului obținem șirul $9$ $8$ $7$ $3$ $2$ care nu conține vreo secvență munte.