Problem : 4 - 串珠珠問題

Problem Statistics

Solved Member: 45　　Submission: 229　　User Tried: 51

Statement:

你有一排珠子整整齊齊的由左到右排成一列，你將它們標號為1,2,3,...,N，並準備把它串成一個手環送給你妹妹。不幸的，你妹妹並不滿意你玩太多遊戲不理他，所以傲嬌地把你的珠子弄亂了。

你看到的時候很囧，因為珠子可能有數十萬個之多，要排成原本的順序可真費事。所以你決定將他排成至少可以串成環狀的樣子就好。你排序這些珠子有幾個規則：

1.每次可以任意交換相鄰的兩個珠子。
2.珠子有分正反兩面，你希望他在正面的時候都夠是一個瞬時針由1排到N的環狀手鍊。
3.你妹妹只有把左右順序弄亂，現在所有珠子都是正面朝上。

因此，你發現你只要將他排成a,a+1,a+2,...,n,1,2,....,a-1的順序就可以串回原本的手環。

例如說你現在看到的珠子編號由左到右分別是：

3 5 4 2 1

交換了4,5兩顆珠子

3 4 5 2 1

交換1,2兩顆珠子

3 4 5 1 2

排好的串珠如圖所式，其中沒有線連接的地方恰好為頭和尾。
對於這個順序，你最少需要交換2次。請你寫個程式，算一下你至少要交換幾次才能夠達成上述條件。

Input:Output:

每筆測資共有2行。第一行是一個整數N(1 <= N <= 100000)。第二行有N個數字，代表現在珠子由左到右的編號，每兩個編號中間用一個空白區隔。

一個整數，代表你最少要交換幾次。

Sample Input:Sample Output:

5
3 5 4 2 1

HINT:

1.跟你妹計較就輸了。
2.醒醒吧，你根本就沒有妹妹。

評分資訊：

30% : n<=5
50% : n<=200
70% : n<=1000
100% : n<=100000

Source:

USACO 2010 Nov. Gold

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	10
2	1000ms	65536kb	10
3	1000ms	65536kb	10
4	1000ms	65536kb	10
5	1000ms	65536kb	10
6	1000ms	65536kb	10
7	1000ms	65536kb	10
8	1000ms	65536kb	10
9	1000ms	65536kb	10
10	1000ms	65536kb	10