407387: GYM102780 K Parabolic sorting

Professor R. is the greatest specialist in the field of discrete mathematics. He has already got bored with all the standard sorting algorithms, and has come up with a new algorithm — the parabolic array sorting algorithm.

Let there be an array of $$$N$$$ different integer numbers $$$a_i$$$. We want to sort it in such a way that the first part of the array strictly decreases, and the second part of the array strictly increases. In this case, we can only interchange the neighboring elements. Both the first and second parts of the array can be of zero length. The professor is interested in the following question: what is the minimum number of actions we need?

In the input $$$N+1$$$ there is a number, the first of which is $$$N$$$ $$$(1 \le N \le 10^5)$$$. Then follow the numbers $$$a_i$$$, whose module does not exceed $$$10^9$$$.

Print a single number — the answer to the problem.

4 2 3 1 4

1

5 3 2 1 4 5

0