温馨提示

本题为上一题的加强版，仅数据范围不同！

题目描述

买完月饼回来的小Z在回家的路上突然发现自己家的楼梯变成了一根根的石柱，想要到达自己家就必须将石柱的高度按照从小到大排序，排序后的石柱高度是一个非严格单调递增的序列，这样他才能一步一步爬到自己家。

小Z力气很小每次只能调换相邻的两块石柱，每调换一次石柱需要搬 $3$ 次石柱（假设我们有高度分别为 $a_i$ 与 $a_j$ 的两根相邻的石柱需要调换位置，他首先要将第 $i$ 根石柱搬到一旁，再将第 $j$ 根石柱搬到原来第 $i$ 根石柱的那个位置，再将一旁的第 $i$ 根石柱搬到原来第 $j$ 根石柱的那个位置）。

小Z不想花费太多力气，请帮他算出最少需要搬几次石柱。

输入格式

输入共两行，第一行输入一个正整数 $n$ 代表石柱的根数 ($1$ $\le$ $n$ $\le$ $10^6$)。

第二行有 $n$ 个正整数 $a_i$ 代表第 $i$ 根石柱的高度 ($1$ $\le$ $a_i$ $\le$ $10^6$)。

输出格式

输出最少需要搬几次石柱

样例

4
1 3 2 4

3

样例 1 解释

第 $2,3$ 根石柱不满足非严格单调递增，故调换第 $2,3$ 根石柱，所以一共要搬 $3$ 次石柱

4
1 3 3 4

0

样例 2 解释

所有的石柱均已按照非严格单调递增的顺序排列，故不需要调换，所以答案为 $0$ 。