A coincidence

A coincidence

Alex is bored and, having nothing to do, he took n dice, numbered them from 1 to n, shuffled them, and placed in a random order. So he started stirring dice over and over again and look if he has got a permutation he had the first time. But there was a lot of dice, he still couldn't get the desired permutation, so Alex became bored again.

So Alex thought about it and decided to get the desired permutation in a different way. He has placed dice in order from 1 to n and decided to select a portion of dice repeatedly, stir them and then return to the same place, but maybe in a different order. He decided to do so until he got the exact same permutation he memorized in the beginning, but before that he wants to know how much time, on average, it takes to get the desired permutation? Alex wants to get it as soon as possible and selects dice to shuffle respectively.


The first line contains an integer n. The second line contains n integers from 1 to n - the permutation, which Alex wants to get.


Print a single number - the average number of shuffles Alex needs to get the desired permutation.

Time limit 1 second
Memory limit 128 MiB
Input example #1
2 1 3
Output example #1

Example description: In the first example, Alex shuffles the first two dice every time. After each shuffle there is a 1/2 chance that dice will swap, and this process will be over. On average, this happens after two shuffles.

Author Евгений Капун
Source 2014 Kharkiv Winter School