제3회 디미고 프로그래밍 챌린지 오픈 콘테스트

디미고 운동장 너머에는 식물을 기르는 스마트팜이 있다. 스마트팜의 관리자 ecode는 1번 품종부터 N번 품종까지의 N가지 식물을 스마트팜에서 기르고 있다. 스마트팜에는 N개의 식물이 겹치는 품종 없이 일렬로 심어져 있다. 그러나 식물들이 마구잡이로 심어져 있어 불편함을 느낀 ecode는 식물을 자신이 원하는 위치로 옮기기로 했다.

스마트팜의 또다른 관리자 ibasic은 ecode의 작업을 도와줄 로봇을 가져왔다. 로봇은 다음과 같은 작업을 실행하여 식물의 위치를 바꾼다.

• 첫 번째 식물과 두 번째 식물을 비교하여 첫 번째 식물의 품종 번호가 더 크면 자리를 바꾼다.

• 두 번째 식물과 세 번째 식물을 비교하여 두 번째 식물의 품종 번호가 더 크면 자리를 바꾼다.

• ⋯

• N−1번째 식물과 N번째 식물을 비교하여 N−1번째 식물의 품종 번호가 더 크면 자리를 바꾼다.

로봇을 많이 사용하면 전기세가 많이 나오기 때문에 ecode는 로봇을 가능한 적게 사용하고 싶다. ecode를 위해 로봇이 모든 작업을 마친 후 M번 품종의 식물이 K번 위치에 있게 하려면 로봇의 작업을 최소 몇 번 실행해야 하는지 출력하는 프로그램을 작성하시오.