문제

altertain은 카드를 오름차순으로 정렬하고 있는 중이다. 일렬로 늘어놓은 카드 중에서 두 장을 골라서 서로 위치를 바꾸는 작업(교환)을 통해 카드를 정렬하고 있다. 그리고 그는 가장 적은 교환을 통해 카드를 오름차순으로 정렬하고 싶어한다.

어린이는 카드 정렬을 방해하고 있는 중이다. altertain이 한 번 카드를 바꾸고 나면 어린이도 카드를 한 번 바꿔서 altertain의 정렬을 방해한다. altertain 은 어린이를 혼내는 대신, 어린이의 행동 패턴을 파악해서 어린이를 골려 주려고 한다. 어린이가 방해하는 모습을 유심히 본 altertain은 어린이가 카드의 배치 상태가 어떻든 상관 없이 일정한 패턴으로 카드를 바꾼다는 사실을 발견했다.

카드의 상태와 어린이의 행동 패턴이 주어졌을 때, 최소의 교환으로 카드를 정렬할 수 있는 방법을 찾아서 altertain을 도와주자. 단, 우리의 목적은 어린이를 골려주기 위한 것이므로 어린이가 마지막에 카드를 바꾸면 정렬이 완료되도록 한다.