최적 재정렬

오늘 아쿠아맨은 자신의 거대한 물고기 무리를 정리하기로 했다. 그는 물고기들을 앞에 일렬로 세우고 주의 깊게 살펴보았다.

일렬로 선 물고기는 총 $n$마리이다. 물고기의 가장 중요한 특성은 힘이다. 줄의 앞에서 $i$번째 물고기의 힘은 $a_i$이다. 이 무리는 이상적으로 구성되어 있다. 각 물고기의 힘은 1부터 $n$까지의 정수이고, 두 물고기의 힘은 같지 않다. 즉, 힘의 값들은 순열을 이룬다.

줄의 무질서도는 더 센 물고기가 덜 센 물고기보다 앞에 서 있는 쌍의 개수이다. 다시 말해, $i < j$이고 $a_i > a_j$를 만족하는 번호 쌍 $(i, j)$의 개수가 무질서도이다.

아쿠아맨은 재정렬 명령을 한 번 내릴 수 있다. 명령에서는 1부터 $n$ 사이의 정수 $x$를 하나 고른다. 그러면 물고기들이 새로운 줄을 이룬다. 힘이 $x$보다 작은 물고기가 먼저 서고, 힘이 정확히 $x$인 물고기가 그다음에 서며, 힘이 $x$보다 큰 물고기가 마지막에 선다. 힘이 $x$보다 작은 물고기들과 큰 물고기들은 재정렬 전의 상대적인 순서를 그대로 유지한다. 예를 들어 물고기가 $\{3, 6, 1, 4, 2, 5\}$ 순서로 서 있고 $x = 4$를 고르면, 재정렬 후에는 $\{3, 1, 2, 4, 6, 5\}$ 순서가 된다.

아쿠아맨은 명령을 한 번 내린 뒤 줄의 무질서도가 가능한 한 작아지기를 원한다. 그가 얻을 수 있는 무질서도의 최솟값을 구하라.

첫 줄에는 물고기의 수 $n$이 주어진다 ($1 \le n \le 3\,000\,000$).

둘째 줄에는 줄에 선 물고기들의 힘 $a_1, a_2, \ldots, a_n$이 주어진다. 이 값들은 서로 다르며, 각각 1 이상 $n$ 이하이다 ($1 \le a_i \le n$, 모든 $i \neq j$에 대해 $a_i \neq a_j$).

재정렬 후 얻을 수 있는 무질서도의 최솟값을 한 줄에 출력한다.