Limits 1s, 256 MB

As Captain Jack Sparrow was passing by the Argentine Sea in search of the hidden treasure of the Copper Scroll, he noticed something was off about the direction he was going! Since the copper scroll is really old, anyone can easily mistake it. So he anchored his ship, Black Pearl, on the nearest shore and sat down to solve the issue.

The scroll has a permutation AA of length NN, and its shape is circular, like the sun.

A permutation is a sequence of integers from 1 to NN of length NN containing each number exactly once. For example, [1], [4, 3, 5, 1,  2], and [3, 2, 1] are permutations, and [1, 1], [4, 3, 1], and [2, 3, 4] are not.

The permutation needs to be sorted in ascending order using exactly NN operations. Each operation will have a cost, and Jack wants to know the sum of the total cost of NN operations.

In the ithi^{th}operation —

  • Choose ii ((11 ii NN )) and put ii in ithi^{th} index that means if currently ii is in jthj^{th} index, swap AiA_i and Aj.A_j. The cost for this operation is the minimum distance between index ii and j.j.

The operations have to be done sequentially, which means first 11 has to be put in index 11, then 22 ………, and lastly, nn has to be put in index n.n.

For Example, [3, 2, 4, 1] is the Permutation:

  • First ii==1,1, so 11 needs to be putted in index 11. Currently, 11 is in index 44. So 11 will be putted in index 11, and 33 will be putted in index 44 [1, 2, 4, 3]. Cost = 11 (as it is a circular permutation).

  • Second ii==2,2, so 22 needs to be putted in index 22. Currently, 22 is in index 22. So 22 will be putted in index 22 [1, 2, 4, 3]. Cost = 00.

  • Third ii==3,3, so 33 needs to be putted in index 33. Currently, 33 is in index 44. So 33 will be putted in index 33, and 44 will be putted in index 44 [1, 2, 3, 4]. Cost = 11.

  • Fourth ii==4,4, so 44 needs to be putted in index 44. Currently, 44 is in index 44. So 44 will be putted in index 44 [1, 2, 3, 4]. Cost = 00.

  • Finally, the sum of all the costs ((11++00++11++00==22)) is our cost to sort the permutation.

Now, you have to print the cost to sort the permutation.

Input

First line of the test case contain a single integer, NN— indicating the length of the permutation. Next line of the test case contain NN integers A1,A2,,ANA_1,A_2,…,A_N — separated by single spaces.

1N1051≤N≤10^5

1AiN1≤A_i≤N

Output

Print the single integer number — indicates the minimum cost to sort the permutation in ascending order.

Samples

InputOutput
4
3 2 4 1
2
InputOutput
10
4 6 7 8 9 10 1 3 2 5
25
InputOutput
5
5 2 4 1 3
5

Submit

Login to submit.

Statistics

38% Solution Ratio
Al.6869Earliest, 8M ago
Nusrat1773Fastest, 0.0s
Al.6869Lightest, 4.9 MB
jahid_hridoyShortest, 356B
Toph uses cookies. By continuing you agree to our Cookie Policy.