Problem 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:

  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 \(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

7

stdin

2 7 0
2 5 1 6 7 4 3

stdout

9 7 6 7 8 10 12

General info

ID: 63

Upload: liviu

Input: Console Input

Memory limit: 128MB/128MB

Time limit: 0.15s

Author: Panaete Adrian

Source: ONI 2021 XI-XII: Problema 2

Submissions

Special Submissions