소는 왜 길을 건너갔을까? 10 timer 2s memory 512MB

소가 왜 길을 건너는지는 아직 아무도 해결못한 난제지만,
농부 존의 소들이 길을 자주 건넌다는 것은 너무도 잘 알려진 사실이다.

다만 소들이 길을 건너는 일이 너무 잦아서 건너면서 부딪히는 일도 생기는데, 존은 이 상황을 해결하고 싶다.

농장에는 일자 모양의 길이 있고, 양쪽에 목초지가 각각 N 개씩있다.

소의 종류별로 목초지 구조가 너무 달라서 한 목초지에는 정해진 종류의 소만 방목할 수 있다.

i번 목초지에는 i번 종류의 소만 방목할 수 있다.

소가 길을 건널 때는 자신과 같은 종류의 소를 방목하는 반대편의 목초지로 이동한다.

목초지의 순서가 뒤죽박죽이어서, a 종류의 소와 b 종류의 소가 건너는 길이 교차할 수도 있다.

이때 (a,b)를 "교차하는 쌍"이라고 하자.

존은 교차하는 쌍의 수를 최소화하기 위해 농장을 옮기는 방법을 고안했다.

0 ≤ k < N인 정수 k에 대해, 맨 뒤에 있는 목초지 k개를 맨 앞으로 옮기려고 한다.

예를 들어서, 목초지 번호가 차례대로 3, 7, 1, 2, 5, 4, 6이고 k=2라면, 옮긴 후의 목초지 번호는 4, 6, 3, 7, 1, 2, 5가 된다.

길의 왼쪽에 있는 목초지여도 되고 오른쪽이어도 되지만, 둘 중 하나만 된다.

교차하는 쌍을 최소로 할 수 있도록 존을 도와주자.