애드난은 바쿠에서 가장 큰 신발가게를 소유하고 있다.

n켤레의 신발이 담긴 상자 하나가 가게에 막 도착했다.

한 켤레는 같은 크기의 신발 두 짝, 즉 왼쪽 신발과 오른쪽 신발로 구성되어 있다.

애드난은 2n개의 모든 신발을 하나의 진열대에 나열했는데,

이 진열대에는 총 2n개의 위치가 있고 각 위치는 왼쪽에서 오른쪽으로 0번부터 2n - 1번까지 번호가 붙어있다.

애드난은 이 신발들을 재배열해서 유효한 나열이 되도록 하고 싶다.

나열이 유효하다는 의미는 모든 i(0 ≤ i ≤ n - 1)에 대해 다음 조건들을 만족한다는 것과 동치이다:

- 위치 2_i와 위치 2_i + 1에 있는 신발은 같은 크기이다.

- 위치 2_i에 있는 신발은 왼쪽 신발이다.

- 위치 2_i + 1에 있는 신발은 오른쪽 신발이다.

이를 위해, 애드난은 일련의 교환(swap) 작업들을 할 수 있다.

한번의 교환 작업에서 애드난이 하는 일은, 인접한 두 신발을 골라서 서로 맞바꾸는 것이다(즉, 두 신발을 들어서 서로 상대방이 있던 위치에 내려둔다).

두 신발이 인접하다는 것은 그 둘의 위치가 1 차이나는 경우이다.

신발들이 유효한 나열이 되는데 필요한 교환 작업의 최소 횟수를 구하시오.

Arranging Shoes timer 1s memory 1024MB

Arranging Shoes 1s 1024MB