Problem : 8 - 書櫃

Problem Statistics

Solved Member: 75　　Submission: 214　　User Tried: 86

Statement:

你家是開圖書館的，所以你有一個很長很長的書櫃，上面擺滿書，這些書分別編號1~N。

你的書常常要借給別人，所以常常拿出來又放進去，自然變得很亂。某天你突然想整理你的書櫃，當你在整理書的時候，你發現你可以很輕鬆的把其中一本書擺到最左邊，於是你決定一直都這樣做。

Task:

給你目前書的順序，請問你要把這些書從左到右由1排到N最少需要移動幾次。

Input:Output:

第1行有一個正整數，N，代表你有N(1 <= N <= 300000)本書。
第2~N+1行每一行各有一個數字，依序為目前由左到右書的編號，保證每個數字不會重複。

1個整數，代表由目前的排列最少需要移動幾次才能夠把書移回原來的排列。

Sample Input:Sample Output:

1:
3
3
2
1

2:
4
1
3
4
2

1:
2

2:
2

Source:

COCI 2010/2011 #2

Problem Setter

Nekosyndrome

Testdata:

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