Pentru o permutare p1, p2, …, pN 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.

Cerința

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 BestK.
2. 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 p1, p2, …, pN reprezent^and 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: Best1, Best2, …, BestN.

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 ≤ pi ≤ N pentru orice i cu 1 ≤ i ≤ N și sunt distincte.

Exemplul 1:

Intrare

1 7 1
1 2 5 6 7 4 3

Ieșire

7

Exemplul 2:

Intrare

2 7 0
2 5 1 6 7 4 3

Ieșire

9 7 6 7 8 10 12