新兵がこうした動きを絶え間ない訓練で身につければ、実際の戦闘でもより容易に実行できる。
- ウェゲティウス、『軍事学摘要』第1巻第26章
あなたが指揮する軍隊は、戦況に応じて陣形を変更する必要があります。しかし、陣形の変更に多くの命令が必要だと、急激な戦況の変化に対応できなくなるかもしれません。あなたは陣形の変更における弱点を見つけ、訓練を強化しようとしています。
部隊には から までの番号が付いています。各陣形は 個の部隊を一列に並べたもので、左翼から右翼への順に並べた部隊の番号で表します。1 回の命令で、隣り合う二つの部隊の位置を入れ替えることができます。
あなたが用意した 個の陣形が与えられます。各陣形について、残りの 個の陣形それぞれに変更するために必要な命令回数の最小値を考え、その最大値を求めてください。変更の途中では、与えられた一覧にない陣形を使ってもかまいません。
最初の行に整数 , が空白区切りで与えられます。
続く 行に、各陣形の部隊の番号 が左翼から右翼への順に空白区切りで与えられます。
各陣形の答えを、与えられた順番に 1 行ずつ出力してください。
最初の例では、1 番目と 2 番目の陣形間の変更には最低 回の命令が必要です。1 番目と 3 番目の陣形間には最低 回、2 番目と 3 番目の陣形間には最低 回の命令が必要です。
2 番目の例では、中央の部隊と右翼の端の部隊を一度入れ替えると、もう一方の陣形に変更できます。
