풍수

서쪽에서 동쪽으로 한 줄로 놓인 $N$개의 화분이 있다. 화분에는 번호가 $1$부터 $N$까지 붙어 있다. 각 화분의 높이는 모두 다르며, $i$번 화분은 높이가 $A_i$번째로 낮다. 즉, 배열 $[A_1, A_2, \dots, A_N]$은 $[1, 2, \dots, N]$의 순열이다.

풍수를 공부한 뒤, 화분을 다음과 같이 배치하면 집이 더 건강해진다고 판단하였다. 어떤 정수 $k$가 있어서 $1 \le k \le N$을 만족하고, 모든 $1 \le i < k$에 대해 $A_i > A_{i+1}$이며, 모든 $k \le i < N$에 대해 $A_i < A_{i+1}$이어야 한다. 인접한 두 화분을 서로 바꿀 수 있으며, 이 작업은 0번 이상 할 수 있다. 화분은 깨지기 쉬우므로 교환 횟수를 최소로 하고자 한다. 풍수 규칙을 만족하는 배치를 만들 때 필요한 교환 횟수의 최솟값을 구하라.

첫째 줄에 정수 $N$ ($1 \le N \le 300\,000$)이 주어진다. 둘째 줄에는 $N$개의 정수 $A_1, A_2, \dots, A_N$ ($1 \le A_i \le N$)이 주어진다. 배열 $A$는 $[1, 2, \dots, N]$의 순열이다.

풍수 규칙을 만족하도록 화분을 배치하는 데 필요한 최소 교환 횟수를 한 줄에 출력한다.