**译自 POI 2011 Round 2. Day 2. A「Tree Rotations」**

*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.*

本题的一个加强版将限制改为 $2≤n≤1000000$。测评仍使用原题数据，即 $2≤n≤200000$。

本题严重卡常，请务必使用快读。

Byteasar the gardener is growing a rare tree called Rotatus Informatikus. It has some interesting features:

- The tree consists of straight branches, bifurcations and leaves. The trunk stemming from the ground is also a branch.
- Each branch ends with either a bifurcation or a leaf on its top end.
- Exactly two branches fork out from a bifurcation at the end of a branch - the left branch and the right branch.
- Each leaf of the tree is labelled with an integer from the range $1…n$. The labels of leaves are unique.
- With some gardening work, a so called rotation can be performed on any bifurcation, swapping the left and right branches that fork out of it.

*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)$, such that $a_{i}>a_{j}$ in the corona $a_{i},a_{2},…,a_{n}$.

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.