|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||9||9||6||100.000%|
This task is a harder version of task Tree Rotations from the second stage of 18th Polish OI. It wasn't used in the contest itself.
Byteasar the gardener is growing a rare tree called Rotatus Informatikus. It has some interesting features:
The corona of the tree is the sequence of integers obtained by reading the leaves' labels from left to right.
Byteasar is from the old town of Byteburg and, like all true Byteburgers, praises neatness and order. He wonders how neat can his tree become thanks to appropriate rotations. The neatness of a tree is measured by the number of inversions in its corona, i.e. the number of pairs (i,j), 1 ≤ i < j ≤ n such that ai > aj in the corona a1,a2,…,an.
The original tree (on the left) with corona 3,1,2 has two inversions. A single rotation gives a tree (on the right) with corona 1,3,2, which has only one inversion. Each of these two trees has 5 branches.
Write a program that determines the minimum number of inversions in the corona of Byteasar's tree that can be obtained by rotations.
In the first line of the standard input there is a single integer n (2 ≤ n ≤ 1,000,000) that denotes the number of leaves in Byteasar's tree. Next, the description of the tree follows. The tree is defined recursively:
In tests worth at least 30% of the points it additionally holds that n ≤ 5,000.
In the first and only line of the standard output a single integer is to be printed: the minimum number of inversions in the corona of the input tree that can be obtained by a sequence of rotations.
3 0 0 3 1 2
Figure 1 illustrates the tree given in the example.