오르막길과 내리막길

숫자가 적힌 카드 여러 장이 탁자 위에 나란히 놓여 있다.

카드의 순서를 바꿔서 앞부분은 적힌 수가 감소하지 않도록, 나머지 부분은 증가하지 않도록 만들려고 한다. 예를 들어 (1, 2, 3, 2, 1), (1, 1, 3, 4, 5, 9, 2), (5, 3, 1)은 가능한 순서지만 (8, 7, 9)와 (5, 3, 5, 3)은 불가능하다.

형식적으로, 카드의 수를 $n$, 순서를 바꾼 후 $i$번째 위치($1 \le i \le n$)에 놓인 카드에 적힌 수를 $b_i$라 하자. 이때 $(b_i \le b_{i+1}\ \forall i \in \{1, \ldots, k-1\})$이고 $(b_i \ge b_{i+1}\ \forall i \in \{k, \ldots, n-1\})$인 $k \in \{1, \ldots, n\}$가 존재해야 한다.

순서를 바꿀 때 허용되는 연산은 인접한 두 카드의 위치를 맞바꾸는 것뿐이다. 주어진 순서를 완성하는 데 필요한 최소 교환 횟수를 구하자.

입력은 다음과 같은 형식의 테스트 케이스 하나로 이루어진다.

n
a1 . . . an

첫 줄의 정수 $n$은 카드의 수이다($1 \le n \le 100\ 000$). 둘째 줄의 정수 $a_1$부터 $a_n$은 원래 위치 순서대로 카드에 적힌 수이다($1 \le a_i \le 100\ 000$).

카드를 지정된 순서로 바꾸는 데 필요한 최소 교환 횟수를 한 줄에 출력한다.