到老舊的火車站你也許會遇到少數僅存的"車箱置換員",車箱置換員是車站的員工,他的工作是重新排列火車車箱。
當每節車箱(尤其是裝貨的車箱)都經過適當的排列之後,火車司機在每個車站卸貨時只需從最後車箱一節一節依序放下即可。
"車箱置換員"的職稱起源於一座位於河畔的火車站,鐵路橫跨在河的兩岸,當船隻要通行時,橋上的鐵路不像其他地方一樣會垂直升起,而是以河中央的橋墩為中心旋轉90度,此時船隻可從橋的左右兩旁經過。
另外,首位車箱置換員發現一件有趣的事,當橋在作旋轉時最多可乘載兩節車箱的重量,所以當橋作180度的旋轉之後,其上的車箱就被掉換位置了,因此他就能重新排列車箱(副作用就是車箱前後位置會相反,不過因為車箱被設計成可以前後移動,所以無所謂)。
現在幾乎所有車箱置換員都死光了,鐵路公司必須做車箱掉換的自動化,需要寫一個程式來計算共需置換相鄰的車箱幾次才能使所有車箱依序排好,寫程式的工作就交給你了。
輸入說明:
第一列有一個整數表示接下來有N組測試資料,每組測試資料兩列,第一列是一個整數L,為車箱的長度,第二列為整數1~L的一種排列組合,表示車箱的起始位置,最後車箱要依照編號1到L的順序依序排好。
輸出說明:
每一列請輸出 'Optimal train swapping takes S swaps.',S為一整數,表示最少需要做幾次車箱置換的步驟。
輸入範例:
3
3
1 3 2
4
4 3 2 1
2
2 1
輸出範例:
Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.