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 of length , and its shape is circular, like the sun.
A permutation is a sequence of integers from 1 to of length 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 operations. Each operation will have a cost, and Jack wants to know the sum of the total cost of operations.
In the operation —
The operations have to be done sequentially, which means first has to be put in index , then ………, and lastly, has to be put in index
For Example, [3, 2, 4, 1] is the Permutation:
First so needs to be putted in index . Currently, is in index . So will be putted in index , and will be putted in index [1, 2, 4, 3]. Cost = (as it is a circular permutation).
Second so needs to be putted in index . Currently, is in index . So will be putted in index [1, 2, 4, 3]. Cost = .
Third so needs to be putted in index . Currently, is in index . So will be putted in index , and will be putted in index [1, 2, 3, 4]. Cost = .
Fourth so needs to be putted in index . Currently, is in index . So will be putted in index [1, 2, 3, 4]. Cost = .
Finally, the sum of all the costs 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, — indicating the length of the permutation. Next line of the test case contain integers — separated by single spaces.
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 |