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

Poveste şi cerinţă...

Pentru o permutare $p{~1~}, p{~2~}, . . . , p{~N~}$ a numerelor de la $1$ la $N$ şi o poziţie $K$, ( $1 ≤ K ≤ N$ ), notăm cu $Best{~K~}$ numărul minim de interschimbări (a valori situate pe poziţii consecutive) necesare pentru a se obţine o permutare descrescătoare de la poziţia $1$ la poziţia $K$ şi crescătoare de la poziţia $K$ la poziţia $N$. Se dă o permutare. Se cere să se rezolve una dintre următoarele două cerinţe:
1. Pentru o poziţie $K$ dată să se calculeze $Best{~K~}$.
2. Pentru toate poziţiile $K$ de la $1$ la $N$ să se calculeze $Best{~K~}$.

h2. Date de intrare

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

Fişierul de intrare $bisortare.in$ va conţine pe prima linie trei numere întregi separate prin spaţiu $C$, $N$ şi $K$. $C$ reprezintă cerinţa şi poate lua valoarea $1$ sau valoarea $2$. $N$ reprezintă ordinul (lungimea) permutării. Dacă $C = 1$ atunci $1 ≤ K ≤ N$ reprezintă poziţia pentru care trebuie calculat $Best{~K~}$. Dacă $C = 2$ atunci $K = 0$ şi $Best{~K~}$ trebuie calculat pentru toate poziţiile de la $1$ la $N$. A doua linie conţine $N$ numere întregi separate prin spaţiu $p{~1~}, p{~2~}, . . . , p{~N~}$ reprezentând elementele permutării.

h2. Date de ieşire

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

În fişierul de ieşire $bisortare.out$ se va afla raspunsul după cum urmează. Dacă $C = 1$ se va rezolva cerinţa $1$. În acest caz pe prima linie se va afişa un singur număr: $Best{~K~}$. Dacă $C = 2$ se va rezolva cerinţa $2$. În acest caz pe prima linie se vor afişa $N$ numere separate prin spaţiu: $Best{~1~}, Best{~2~}, . . . , Best{~N~}$

h2. Restricţii

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

* $1 ≤ C ≤ 2$
* $1 ≤ N ≤ 100000$
* Dacă $C = 1$, atunci $1 ≤ K ≤ N$
* Dacă $C = 2$, atunci $K = 0$
* $1 ≤ p{~i~} ≤ N$, pentru orice $i$ cu $1 ≤ i ≤ N$ şi sunt distincte
 
h2. Subtaskuri
 
* *Subtask 1 (3 puncte)*
** $C = 1, N ≤ 3000, K = 1$
 
* *Subtask 2 (3 puncte)*
** $C = 1, N ≤ 100000, K = 1$
 
* *Subtask 3 (3 puncte)*
** $C = 1, N ≤ 3000, K = N$
 
* *Subtask 4 (3 puncte)*
** $C = 1, N ≤ 100 000, K = N$
 
* *Subtask 5 (9 puncte)*
** $C = 2, N ≤ 8$
 
* *Subtask 6 (11 puncte)*
** $C = 2, N ≤ 18$
 
* *Subtask 7 (13 puncte)*
** $C = 2, N ≤ 60$
 
* *Subtask 8 (14 puncte)*
** $C = 2, N ≤ 200$
 
* *Subtask 9 (15 puncte)*
** $C = 2, N ≤ 3000$
 
* *Subtask 10 (26 puncte)*
** $C = 2, N ≤ 100000$

h2. Exemplu
table(example). |_. bisortare.in |_. bisortare.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie

| 1 7 1
1 2 5 6 7 4 3
| 7 |
| 2 7 0
2 5 1 6 7 4 3
| 9 7 6 7 8 10 12 |

...

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