Because of necessary software maintenance, Jutge.org may not fully work on the 7 of may, from 8 to 10 CEST.

Intercanvis P58715

Statement

html

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 ≤ 10⁵.

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

Information

Author: Salvador Roura
Language: Catalan
Official solutions: C++
User solutions: C++