## DMOPC '16 Contest 1 P5 - Blood Tubes

View as PDF

Points: 12 (partial)
Time limit: 0.6s
Memory limit: 64M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

A few days back, Gigel had to take the yearly blood test which he had avoided for too long. While waiting to be pricked by the needle, he saw the nurse arranging blood tubes on a nearby table in a certain order. This helped him get through this struggle (as he is afraid of needles), since he came up with a problem to distract him. He quickly went home and wrote a draft for it:

A nice nurse brings you a permutation of blood tubes numbered from to . You need to place them on the table one by one and form a series with the minimum number of inversions. Each blood tube can only be placed in the beginning or the end of the blood tubes on the table. For example, if you have the blood tube in your hand and the tubes on the table, after you place it on the table, you can only have or as possible series. Considering and the element on the position , an inversion is when and .

Gigel already knows the solution, but he likes seeing other people's approaches, so he asks you to try to solve this problem.

#### Input Specification

On the first line of input you find (), and on the next line you find space-separated integers which represents the initial permutation.

#### Output Specification

On the first line you must print the minimum number of inversions.

#### Sample Test 1

##### Sample Input
4
2 1 3 4
##### Sample Output
0

#### Sample Test 2

##### Sample Input
4
2 1 4 3
##### Sample Output
1