신병들이 이러한 기동을 꾸준한 훈련으로 익히면 실제 전투에서도 더 쉽게 수행할 수 있다.
- 베게티우스, 『군사학 논고』 제1권 26장
당신이 지휘하는 군대는 전황에 따라 진형을 바꾸어야 한다. 그러나 진형을 바꾸는 데 많은 명령이 필요하면 급변하는 전황에 대응하기 어렵다. 당신은 진형 전환의 취약점을 찾아 훈련을 보강하려 한다.
부대에는 번부터 번까지 번호가 붙어 있다. 각 진형은 개 부대를 일렬로 배치한 것으로 좌익에서 우익으로 차례대로 나열한 부대 번호로 나타낸다. 명령 한 번으로 이웃한 두 부대의 위치를 맞바꿀 수 있다.
당신이 마련한 진형 개가 주어진다. 각 진형에 대해 나머지 개 진형으로 전환하는 데 필요한 최소 명령 횟수의 최댓값을 구하여라. 전환 도중에는 주어진 목록에 없는 진형을 사용해도 된다.
첫째 줄에 정수 , 이 공백으로 구분되어 주어진다.
다음 개의 줄에 각 진형의 부대 번호 가 좌익에서 우익의 순서로 주어진다. 각 번호는 공백으로 구분되어 있다.
각 진형의 답을 주어진 순서대로 한 줄에 하나씩 출력한다.
첫 번째 예제에서 첫 번째와 두 번째 진형 사이의 전환에는 최소 번의 명령이 필요하다. 첫 번째와 세 번째 진형 사이에는 최소 번이 필요하고 두 번째와 세 번째 진형 사이에는 최소 번이 필요하다.
두 번째 예제에서는 가운데 부대와 우익 끝의 부대의 위치를 한 번 맞바꾸면 다른 진형으로 전환할 수 있다.
