소는 왜 길을 건넜을까

소는 왜 길을 건넜을까? 그 완전한 이유는 영영 알 수 없을지 모르지만, 농부 존의 소들이 실제로 길을 꽤 자주 건넌다는 것만은 확실하다. 사실 소들은 길을 너무 자주 건너다 보니 경로가 교차할 때 서로 부딪히는 일이 잦은데, 농부 존은 이 상황을 해결하고 싶어 한다.

농부 존은 \(N\)개 품종의 소를 키우며 (\(1 \leq N \leq 100,000\)), 각 들판은 특정 품종 하나만의 방목지로 지정되어 있다. 예를 들어 품종 12로 지정된 들판은 품종 12의 소만 사용할 수 있고 다른 품종은 사용할 수 없다. 농장을 가로질러 긴 도로가 지나간다. 도로의 한쪽에는 \(N\)개의 들판이 순서대로 놓여 있고(품종마다 하나씩), 도로의 다른 쪽에도 \(N\)개의 들판이 순서대로 놓여 있다(역시 품종마다 하나씩). 따라서 소가 도로를 건널 때는 자신의 품종으로 지정된 두 들판 사이를 건너게 된다.

농부 존이 좀 더 신중하게 계획했다면 도로 양쪽의 들판을 품종별로 같은 순서로 배치했을 것이고, 그러면 각 품종의 두 들판이 도로를 사이에 두고 정확히 마주 보게 되었을 것이다. 그랬다면 서로 다른 품종의 소들이 부딪히는 일 없이 도로를 건널 수 있었을 것이다. 하지만 아쉽게도 도로 양쪽의 순서가 다를 수 있으므로, 농부 존은 교차하는 품종 쌍이 있을 수 있음을 알게 된다. 서로 다른 두 품종의 쌍 \((a,b)\)는, 품종 \(a\)가 도로를 건너는 어떤 경로든 품종 \(b\)가 도로를 건너는 어떤 경로와든 반드시 교차해야 한다면 "교차" 쌍이다.

농부 존은 교차하는 품종 쌍의 수를 최소화하고 싶어 한다. 물류상의 이유로, 그는 도로 한쪽의 소들을 옮겨 그쪽 들판들에 "순환 이동"을 적용할 수 있다고 생각한다. 즉, 어떤 \(0 \leq k < N\)에 대해 모든 소가 자기 들판보다 \(k\)칸 앞의 들판으로 이동하고, 마지막 \(k\)개 들판의 소들은 처음 \(k\)개 들판을 채우도록 이동한다. 예를 들어 도로 한쪽 들판들이 품종 순서로 3, 7, 1, 2, 5, 4, 6이었는데 \(k=2\)의 순환 이동을 적용하면 새 순서는 4, 6, 3, 7, 1, 2, 5가 된다. 도로 한쪽의 들판들에 적절한 순환 이동을 적용한 뒤 존재할 수 있는 교차 품종 쌍의 최소 개수를 구하시오.

문제 출처: Brian Dean

문제 출처: Brian Dean

입력의 첫째 줄에 \(N\)이 주어진다. 다음 \(N\)개의 줄은 도로 한쪽 들판들의 순서를 품종 ID로 나타낸다. 각 품종 ID는 \(1 \ldots N\) 범위의 정수이다. 마지막 \(N\)개의 줄은 도로 다른 쪽 들판들의 순서를 품종 ID로 나타낸다.

도로 한쪽(어느 쪽이든 가능)의 들판들에 순환 이동을 적용한 뒤의 교차 품종 쌍의 최소 개수를 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > February > Platinum