신발 정리

애드난은 바쿠에서 가장 큰 신발 가게를 운영한다. 같은 크기의 왼쪽 신발과 오른쪽 신발로 이루어진 $n$켤레, 즉 $2n$개의 신발이 도착했다. 애드난은 신발을 왼쪽부터 $0$번에서 $2n-1$번까지의 위치에 한 줄로 놓았다.

다음 조건을 모든 $i$ ($0 \leq i \leq n-1$)에 대해 만족하는 배열을 올바른 배열이라고 한다.

• 위치 $2i$와 $2i+1$의 신발 크기가 같다.
• 위치 $2i$에는 왼쪽 신발이 있다.
• 위치 $2i+1$에는 오른쪽 신발이 있다.

애드난은 현재 서로 인접한 두 신발을 골라 맞바꾸는 작업을 여러 번 할 수 있다. 두 위치의 차이가 $1$이면 두 신발은 인접한다.

신발을 올바르게 배열하는 데 필요한 인접 교환의 최소 횟수를 구하여라.

구현 세부 사항

다음 함수를 구현해야 한다.

long long count_swaps(vector<int> S)

• $S$: 길이가 $2n$인 정수 배열이다.
• $|S[i]|$는 위치 $i$에 놓인 신발의 크기이며 $0$이 아니다.
• $S[i] < 0$이면 왼쪽 신발이고, $S[i] > 0$이면 오른쪽 신발이다.
• 올바른 배열을 만드는 데 필요한 인접 교환의 최소 횟수를 반환해야 한다.

예제

예제 1

다음 호출을 생각해 보자.

count_swaps([2, 1, -1, -2])

신발 $1$과 $-1$, $1$과 $-2$, $-1$과 $-2$, $2$와 $-2$를 차례로 교환하면 $[-2,2,-1,1]$을 얻는다. 네 번보다 적은 교환으로는 올바른 배열을 만들 수 없으므로 반환 값은 $4$이다.

예제 2

count_swaps([-2, 2, 2, -2, -2, 2])

위치 $2$와 $3$의 신발을 한 번 교환하면 $[-2,2,-2,2,-2,2]$가 되므로 반환 값은 $1$이다.

제한

• $1 \leq n \leq 100\,000$
• 모든 $i$ ($0 \leq i \leq 2n-1$)에 대해 $1 \leq |S[i]| \leq n$
• 어떤 교환 순서를 사용하면 반드시 올바른 배열을 만들 수 있다.

부분 문제

1. (10점) $n=1$
2. (20점) $n \leq 8$
3. (20점) 모든 신발의 크기가 같다.
4. (15점) 위치 $0,\ldots,n-1$에는 모두 왼쪽 신발이, 위치 $n,\ldots,2n-1$에는 모두 오른쪽 신발이 있다. 또한 위치 $i$와 $i+n$의 신발 크기가 같다.
5. (20점) $n \leq 1000$
6. (15점) 추가 제한이 없다.

• 첫째 줄: $n$
• 둘째 줄: $S[0]\;S[1]\;\ldots\;S[2n-1]$

• count_swaps의 반환 값을 한 줄에 출력한다.