== include(page="template/taskheader" task_id="risc2") ==

Poveste şi cerinţă...

Pentru a participa la un concert, *n* persoane s-au aşezat la coadă pe un singur rând în aşteptarea deschiderii casei de bilete. Înălţimile celor n persoane sunt toate distincte. Pe baza acestei informaţii cruciale, agenţii de securitate au decis ca din motive de ... securitate, ordinea persoanelor care aşteaptă la coadă trebuie schimbată în funcţie de înălţimile lor.
Astfel, agentii de pază vor alege, pe rând, câte o persoană şi o vor trimite la sfârşitul rândului. După fiecare operaţie de tipul acesta, să-i spunem “de mutare”, rândul se restrânge, ocupându-se poziţia rămasă liberă. Strategia agenţilor de pază este aceasta: la terminarea tuturor operaţiilor de mutare, _*riscul minim de securitate*_ se obţine dacă toate persoanele aflate în dreapta persoanei celei mai înalte vor fi mai înalte decât cele aflate în stânga persoanei cele mai înalte. În plus, înalţimile persoanelor vor fi crescătoare până la poziţia *k* a persoanei celei mai înalte şi descrescătoare după poziţia *k*.
Mai exact: dacă *h ~1~, h ~2~, …, h ~n~* sunt înălţimile persoanelor după finalizarea operaţiilor de mutare, atunci: există o poziţie *k*, cu *1 ≤ k ≤ n* astfel încât *h ~1~ < h ~2~ < ... h ~k-1~ < h ~k~ > h ~k+1~ > … > h ~n-1~ > h ~n~* şi în plus *h ~i~ < h ~j~* pentru oricare *i < k* şi *k < j*.
Deoarece o asemenea logică este greu de combătut, iar agenţii nu au aerul că vor să glumească, persoanele care aşteaptă la coadă vor accepta toate mutările impuse de către aceştia.
 
h2. Cerinte
 
Cunoscând numărul de persoane *n* şi înălţimile *h ~1~, h ~2~, …, h ~n~* ale acestora să se scrie un program care determină :
*1.* Poziţia persoanei celei mai înalte în rândul iniţial, în cazul în care nu sunt necesare operaţii de mutare.
*2.* Numărul minim de mutări necesare pentru ca rândul de persoane să prezinte un risc minim de securitate.

h2. Date de intrare

Fişierul de intrare $risc2.in$ ...

Pe prima linie a fişierului de intrare *risc2.in* se găseşte numărul natural *p* a cărui valoare poate fi doar *1* sau *2*.
Pe a doua linie a fişierului de intrare se află numărul natural *n* cu semnificaţia din enunţ.
Pe a treia linie se găsesc *n* numere naturale, distincte: *h ~1~, h ~2~, …, h ~n~*, separate prin câte un singur spaţiu, reprezentând înălţimile persoanelor.

h2. Date de ieşire

În fişierul de ieşire $risc2.out$ ...

Fişierul de ieşire este *risc2.out*.
 
* Dacă valoarea lui *p* este *1* atunci *se va rezolva numai cerinţa 1*. În acest caz, fişierul de ieşire va conţine pe prima linie un număr natural *poz* ce reprezintă poziţia persoanei celei mai înalte în rândul iniţial. Dacă rândul iniţial nu respectă condiţiile de _risc minim de securitate_, atunci *poz* este *-1*.
* Dacă valoarea lui *p* este *2* atunci *se va rezolva numai cerinţa 2*. În acest caz fişierul de ieşire va conţine pe prima linie *un număr* natural *m*, reprezentând numărul minim de mutări necesare pentru a obţine _risc minim de securitate_.

h2. Restricţii

* $... ≤ ... ≤ ...$

* *1 ≤ n ≤ 100 000*
* *1 ≤ *h ~1~, h ~2~, …, h ~n~* ≤ 100 000*
* Persoana cea mai înaltă într-o configuraţie cu _risc minim de securitate_ poate fi plasată pe oricare dintre poziţiile *1...n*
* Pentru *50%* din teste, *n ≤ 2000*, iar pentru alte *40%* din teste, *n ≤ 10 000*
* Pentru rezolvarea corectă a primei cerinţe se acordă *20* de puncte, iar pentru cerinţa a doua se acordă *80* de puncte.

h2. Exemplu

table(example). |_. risc2.in |_. risc2.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

table(example). |_. risc2.in |_. risc2.out |_. Explicatie |
| 1
4
35 20 10 1
| 1
| p = 1, deci se rezolvă *numai cerinţa 1*.
Rândul îndeplineşte condiţiile de risc minim de securitate.
Persoana cea mai înaltă se găseste pe poziţia poz = 1.

|

 
h3. Explicaţie
 
...

|1
6
1 8 12 20 15 10
|-1
|p = 1, deci se rezolvă *numai cerinţa 1*.
Rândul *NU* îndeplineşte condiţiile de risc minim de securitate.
Şirul înălţimilor nu respectă condiţia ca toate valorile înălţimilor din dreapta poziţiei persoanei celei mai înalte să fie
mai mari decât toate valorile înălţimilor din stânga acesteia.
Deci poz = -1.
|
|2
5
2 8 4 20 16
|1
|p = 2, deci se rezolvă *numai cerinţa 2*.
Se mută persoana de înălţime *8* la sfârşitul rândului.
Deci *m = 1*
|
|2
6
3 19 7 30 10 25
|2
|p = 2, deci se rezolvă *numai cerinţa 2*.
Prima operaţie: se mută persoana de înălţime *19* la sfârşitul
rândului. Rândul devine: *3 7 30 10 25 19*
A doua operaţie: se mută persoana de înălţime *10* la sfârşitul
rândului.
Rândul devine: *3 7 30 25 19 10*
Deci *m = 2*
|

== include(page="template/taskfooter" task_id="risc2") ==