바이토닉 정렬

노아는 다음과 같은 카드 게임을 제안한다. 서로 다른 양의 정수가 하나씩 적힌 카드 한 벌이 있다. 카드를 섞어 한 줄로 늘어놓는다. 목표는 카드의 값이 처음에는 단조 증가하다가 나머지 부분에서는 단조 감소하도록 카드를 줄에 배열하는 것이다.

허용되는 이동은 이웃한 두 카드가 자리를 바꾸는 것뿐이다. 카드는 서로 이웃해 있을 때만 자리를 바꿀 수 있다.

최종 배열에서 증가하는 앞부분은 비어 있어도 되고(즉, 전체가 내림차순이어도 되며), 감소하는 뒷부분도 비어 있어도 된다.

카드를 올바른 순서로 배열하는 데 필요한 최소 이동 횟수는 얼마인가?

첫째 줄에 정수 $n$ ($1 \le n \le 3 \cdot 10^5$)이 주어진다. 이는 카드의 수이다.

다음 $n$개 줄에 각각 정수 $c$ ($1 \le c \le 10^9$)가 하나씩 주어진다. 이는 처음 순서대로 나열된 카드이다. 모든 값은 서로 다르다.

카드를 지정된 순서로 배열하는 데 필요한 최소 이동 횟수를 정수 하나로 출력한다.