문제
애드난은 바쿠에서 가장 큰 신발가게를 소유하고 있다.
n켤레의 신발이 담긴 상자 하나가 가게에 막 도착했다.
한 켤레는 같은 크기의 신발 두 짝, 즉 왼쪽 신발과 오른쪽 신발로 구성되어 있다.
애드난은 2n개의 모든 신발을 하나의 진열대에 나열했는데,
이 진열대에는 총 2n개의 위치가 있고 각 위치는 왼쪽에서 오른쪽으로 0번부터 2n - 1번까지 번호가 붙어있다.
애드난은 이 신발들을 재배열해서 유효한 나열이 되도록 하고 싶다.
나열이 유효하다는 의미는 모든 i(0 ≤ i ≤ n - 1)에 대해 다음 조건들을 만족한다는 것과 동치이다:
- 위치 2i와 위치 2i + 1에 있는 신발은 같은 크기이다.
- 위치 2i에 있는 신발은 왼쪽 신발이다.
- 위치 2i + 1에 있는 신발은 오른쪽 신발이다.
이를 위해, 애드난은 일련의 교환(swap) 작업들을 할 수 있다.
한번의 교환 작업에서 애드난이 하는 일은, 인접한 두 신발을 골라서 서로 맞바꾸는 것이다(즉, 두 신발을 들어서 서로 상대방이 있던 위치에 내려둔다).
두 신발이 인접하다는 것은 그 둘의 위치가 1 차이나는 경우이다.
신발들이 유효한 나열이 되는데 필요한 교환 작업의 최소 횟수를 구하시오.
입력
1번 줄 : n
2번 줄 : S0 S1 ... S2n-1
- S : 2n개의 정수로 구성된 배열. 각 i(0 ≤ i ≤ 2n - 1)에 대해, |Si|는 초기에 위치 i에 놓여 있는 신발의 크기를 나타내며 0이 아닌 정수이다.
이때 |x|는 x의 절댓값으로, x > 0이면 x와 같고 x < 0이면 -x와 같다.
만약 Si < 0이면, 위치 i에 있는 신발은 왼쪽 신발이다; Si > 0이면 오른쪽 신발이다.
- 1 ≤ n ≤ 100 000
- 각 i (0 ≤ i ≤ 2n - 1)에 대해, 1 ≤ |Si| ≤ n
- 일련의 교환 작업을 통해 신발들의 유효한 나열을 얻을 수 있다.
출력
첫 번째 줄에 유효한 나열이 되는데 필요한 (인접한 신발들의) 교환 작업의 최소 횟수를 출력하여라.
예제1
2
21-1-2
4