11925 - Generating Permutations

由 1, 2, 3, ..., n 的序列開始，經過一些步驟重新排列後，可以得到另一組序列。給定一組目標序列，請你由1, 2, 3, ..., n的序列開始，經由下列兩種操作來得到目標序列：

• 操作 1：對最前面兩個數做交換，例如：3, 2, 4, 5, 1變為2, 3, 4, 5, 1。
• 操作 2：將最前面的數移到最後面，例如由3, 2, 4, 5, 1變為2, 4, 5, 1, 3。

Input

輸入有多組測試資料，每組資料一列，其第一個整數為 n，n值介於1到300之間，接下來共有n個整數表示目標序列。當 n = 0 表示資料結束。

Output

請對每組測試資料輸出一列，表示使原序列(1, 2, 3, ..., n)轉換為目標序列的操作步驟依序為何，請輸出'1'表示執行操作1，輸出'2'表示執行操作2。
輸出的步驟總數並不要求要最小化，但不能超過2n*n次。若不需任何步驟即可產生目標序列，請輸出一列空行。

Sample Input 

3 2 1 3
3 2 3 1
4 4 2 3 1
0

Sample Output 

1
2
12122

---

原文出處