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

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:

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

* Subtask 1 (3 puncte)

* *Subtask 1 (3 puncte)*

** $C = 1, N ≤ 3000, K = 1$

* Subtask 2 (3 puncte)

* *Subtask 2 (3 puncte)*

** $C = 1, N ≤ 100000, K = 1$

* Subtask 3 (3 puncte)

* *Subtask 3 (3 puncte)*

** $C = 1, N ≤ 3000, K = N$

* Subtask 4 (3 puncte)

* *Subtask 4 (3 puncte)*

** $C = 1, N ≤ 100 000, K = N$

* Subtask 5 (9 puncte)

* *Subtask 5 (9 puncte)*

** $C = 2, N ≤ 8$

* Subtask 6 (11 puncte)

* *Subtask 6 (11 puncte)*

** $C = 2, N ≤ 18$

* Subtask 7 (13 puncte)

* *Subtask 7 (13 puncte)*

** $C = 2, N ≤ 60$

* Subtask 8 (14 puncte)

* *Subtask 8 (14 puncte)*

** $C = 2, N ≤ 200$

* Subtask 9 (15 puncte)

* *Subtask 9 (15 puncte)*

** $C = 2, N ≤ 3000$

* Subtask 10 (26 puncte)

* *Subtask 10 (26 puncte)*

** $C = 2, N ≤ 100000$
h2. Exemplu