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 $A$ of length $N$, and its **shape is circular, like the sun**.

A permutation is a sequence of integers from 1 to $N$ of length $N$ 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 $N$ operations. Each operation will have a cost, and Jack wants to know the sum of the total cost of $N$ operations.

In the $i^{th}$operation —

- Choose $i$ $($$1$$≤$ $i$ $≤$ $N$ $)$ and put $i$ in $i^{th}$ index that means if currently $i$ is in $j^{th}$ index, swap $A_i$ and $A_j.$ The cost for this operation is the minimum distance between index $i$ and $j.$

The operations have to be done sequentially, which means first $1$ has to be put in index $1$, then $2$ ………, and lastly, $n$ has to be put in index $n.$

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

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

Second $i$$=$$2,$ so $2$ needs to be putted in index $2$. Currently, $2$ is in index $2$. So $2$ will be putted in index $2$ [1, 2, 4, 3]. Cost = $0$.

Third $i$$=$$3,$ so $3$ needs to be putted in index $3$. Currently, $3$ is in index $4$. So $3$ will be putted in index $3$, and $4$ will be putted in index $4$ [1, 2, 3, 4]. Cost = $1$.

Fourth $i$$=$$4,$ so $4$ needs to be putted in index $4$. Currently, $4$ is in index $4$. So $4$ will be putted in index $4$ [1, 2, 3, 4]. Cost = $0$.

Finally, the sum of all the costs $($$1$$+$$0$$+$$1$$+$$0$$=$$2$$)$ is our cost to sort the permutation.

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

First line of the test case contain a single integer, $N$— indicating the length of the permutation. Next line of the test case contain $N$ integers $A_1,A_2,…,A_N$ — separated by single spaces.

$1≤N≤10^5$

$1≤A_i≤N$

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

Input | Output |
---|---|

4 3 2 4 1 | 2 |

Input | Output |
---|---|

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

Input | Output |
---|---|

5 5 2 4 1 3 | 5 |

Login to submit.

38%
Solution Ratio

Al.6869Earliest,

Nusrat1773Fastest, 0.0s

Al.6869Lightest, 4.9 MB

jahid_hridoyShortest, 356B

Toph uses cookies. By continuing you agree to our Cookie Policy.