Fişierul intrare/ieşire:	bisortare.in, bisortare.out	Sursă	ONSEPI, clasele 11-12
Autor	Adrian Panaete	Adăugată de	Nicola Alexandra Mihaela •Nicolaalexandra
Timp execuţie pe test	0.125 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Bisortare

Pentru o permutare p₁, p₂, . . . , 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.

Date de intrare

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₁, p₂, . . . , p_N reprezentând elementele permutării.

Date de ieşire

Î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₁, Best₂, . . . , Best_N

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

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

Exemplu

bisortare.in	bisortare.out
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

Cum se trimit solutii?