DMOPC '16 Contest 1 P5 - Blood Tubes

View as PDF

Submit solution

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

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 N blood tubes numbered from 1 to N. 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 4 in your hand and the tubes 1\ 3\ 2 on the table, after you place it on the table, you can only have 4\ 1\ 3\ 2 or 1\ 3\ 2\ 4 as possible series. Considering i and p_i the element on the position i, an inversion is when i < j and p_i > p_j.

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 N (1 < N \le 500\,000), and on the next line you find N 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
2 1 3 4
Sample Output

Sample Test 2

Sample Input
2 1 4 3
Sample Output