題目說明

請撰寫一個程式，讀取一個長度為20的整數陣列，數值最小是1，最大是100，陣列的每個元素都不重複。程式需檢查是否可以藉由將陣列以向右旋轉 k 個位置，使其形成遞增排序的陣列。如果可以，輸出最小的 k；如果無法形成遞增排序，則輸出-1。

所謂的向右旋轉是指陣列中每個元素都向右移動 k 個位置，超出陣列末端的元素會放到陣列的左邊。例如： 原始陣列為 3,4,5,6,1,2,7,8，向右旋轉一次(k=1)後變為 8,3,4,5,6,1,2,7。

進階提示：此題的解答不需要使用巢狀迴圈，有低複雜度的簡易解法。

輸入

1. 20個整數，數字之間以空格分隔。
2. 每個整數最小是1而且最大是100，且所有數字均不重複。

輸出

1. 如果找到滿足條件的旋轉步數，輸出該步數 k。
2. 如果無法形成遞增排序陣列，輸出-1。

思考邊界條件時可參考以下提示

• 陣列可能已經是遞增排序（無需旋轉）。
• 陣列可能必須旋轉到最大步數（19步）才能形成遞增排序。
• 陣列中無法藉由任何旋轉形成遞增排序。

範例輸入 #1

78 85 92 98 3 6 11 15 20 25 30 35 40 45 50 55 60 65 70 75

範例輸出 #1

16

範例解釋 #1

向右旋轉16次後，陣列變為遞增排序。

範例輸入 #2

5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100

範例輸出 #2

0

範例解釋 #2

陣列本身已排序，無須旋轉，輸出0。

範例輸入 #3

85 80 75 70 65 60 55 50 45 40 35 30 25 20 15 10 5 3 2 1

範例輸出 #3

-1

範例解釋 #3

無論如何旋轉都無法形成遞增排序，輸出-1。