Intercanvis P58715


Statement
 

pdf   zip

thehtml

Donada una permutació dels nombres entre 1 i n, l’heu d’ordenar de petit a gran. L’única operació que podeu fer és intercanviar dos nombres entre si. Quants intercanvis necessiteu?

Entrada

L’entrada consisteix en diversos casos, cadascun amb n, seguit d’una permutació de { 1, …, n }. Podeu suposar 1 ≤ n ≤ 105.

Sortida

Per a cada cas, escriviu una línia amb el mínim nombre d’intercanvis necessaris.

Public test cases

  • Input

    2  1 2
2  2 1
6  1 2 3 4 5 6
6  6 5 4 3 2 1
5  2 4 5 1 3
1  1

    Output

    0
1
0
3
3
0
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++