risc

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 \leq k \leq 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.

Cerință

Cunoscând numărul de persoane n și înălțimile $h_1, h_2, \dots, 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.

Date de intrare

Pe prima linie a fişierului de intrare risc.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, \dots, h_n$, separate prin câte un singur spaţiu, reprezentând înălțimile persoanelor.

Date de ieșire

Fișierul de ieșire este risc.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$ 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.

Restricții și precizări

• $1 \leq n \leq 100 \ 000$
• $1 \leq h_1, h_2, … h_n \leq 100 \ 000$
• Persoana cea mai înaltă într-o configurație cu risc minim de securitate poate fi plasată pe oricare dintre pozițiile $1, 2, \dots, n$
• Pentru $50\%$ din teste, $n \leq 2 \ 000$, iar pentru alte $40\%$ din teste, $n \leq 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.

Exemplul 1

risc.in

1
4
35 20 10 1

risc.out

1

Explicație

$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$.

Exemplul 2

risc.in

1
6
1 8 12 20 15 10

risc.out

-1

Explicație

$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$.

Exemplul 3

risc.in

2
5
2 8 4 20 16

risc.out

1

Explicație

$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$.

Exemplul 4

risc.in

2
6
3 19 7 30 10 25

risc.out

2

Explicație

$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$.