Problem 63: 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 BestK 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 urmatoarele două cerințe:

Pentru o poziție K dată să se calculeze BestK.
Pentru toate pozițiile K de la 1 la N să se calculeze BestK.

Date de intrare

Prima linie conține 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 BestK. Dacă C = 2 atunci K = 0 și BestK 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.

Date de ieșire

Dacă C = 1 se va rezolva cerința 1. În acest caz pe prima linie se va afișa un singur număr: BestK. 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$ .

Restricții și precizări

1 ≤ C ≤ 2
1 ≤ N ≤ 100 000
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.

Subtask 1 (2 puncte)

C = 1, N ≤ 3000, K = 1

Subtask 2 (4 puncte)

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

Subtask 3 (2 puncte)

C = 1, N ≤ 3000, K = N

Subtask 4 (4 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 ≤ 100 000

Exemple

stdin

1 7 1
1 2 5 6 7 4 3

stdout