Hide

Problem B
Jobbyte

Languages en sv

Du och dina kompisar jobbar alla på olika företag. Dock känner sig kanske inte alla helt nöjda med vad de håller på med. Ni har därför bett JobAgent ta reda på om det finns ett roligare jobb som skulle passa er bättre. Efter en tids beräknande återkommer JobAgent med en lista på vilket jobb som hade varit bäst för var och en av er. Det bästa är att någon i er vänkrets redan jobbar på var och ett av de föreslagna jobben. Som goda medarbetare skulle ni aldrig kunna tänka er lämna ett jobb utan ersättare och aldrig heller vara arbetslösa. Den rimliga lösningen är så klart att upprepade gånger byta jobb med varandra. Hur många gånger måste två personer byta jobb för att alla ska hamna på det jobb som JobAgent föreslagit?

Indata

Den första raden i indatan består av ett heltal $N$ ($2 \le N \le 3\cdot 10^5$), antalet kompisar (inklusive dig själv) som ska byta jobb.

Därefter följer en rad med $N$ heltal. Det $i$’te av dessa heltal innehåller numret på den person som just nu har jobbet som person $i$ är bäst lämpad för. Alla personer är numrerade mellan $1$ och $N$. Det är garanterat att för varje jobb är det exakt en person som är bäst lämpad för jobbet.

Utdata

Ett heltal, det minsta antalet jobbyten som måste göras.

Förklaring av exempel 2

Här har ingen person rätt jobb från början. Tre jobbyten räcker dock för att alla ska få rätt jobb. Först kan de två första personerna byta jobb, så att personerna nu har jobb 3 2 4 1 och person $2$ har rätt jobb. Sedan kan person $3$ och $4$ byta jobb, vilket resulterar i jobben 3 2 1 4. Då har bara personerna $1$ och $3$ fel jobb, och byter med varandra för att slutföra processen.

Sample Input 1 Sample Output 1
3
3 2 1
1
Sample Input 2 Sample Output 2
4
2 3 4 1
3
Sample Input 3 Sample Output 3
2
2 1
1