Description

　　一個叫做立方體大作戰的游戲風靡整個Byteotia。這個游戲的規則是相當復雜的，所以我們只介紹他的簡單規 則：給定玩家一個有2n個元素的棧，元素一個疊一個地放置。這些元素擁有n個不同的編號，每個編號正好有兩個 元素。玩家每次可以交換兩個相鄰的元素。如果在交換之后，兩個相鄰的元素編號相同，則將他們都從棧中移除， 所有在他們上面的元素都會掉落下來并且可以導致連鎖反應。玩家的目標是用最少的步數將方塊全部消除。 Input

　　第一行包含一個正整數n(1<=n<=50000)。接下來2n行每行一個數ai，從上到下描述整個棧，保證每個數出現且 僅只出現兩次(1<=ai<=n)。初始時，沒有兩個相同元素相鄰。并且保證所有數據都能在1000000步以內出解。 Output

　　第一行包含一個數m，表示最少的步數。 Sample Input 樣例輸入1

5

5

2

3

1

4

1

4

3

5

2

樣例輸入2

3

1

2

3

1

2

3

Sample Output 樣例輸出1

2

樣例輸出2

3

解題方法1： 貪心+樹狀數組， 直接從左往右讀入，讀到數字第一次出現的時候記錄位置，第二次出現的時候直接和第一次合并掉。然后這樣貪心為什么是正確的呢？ 下面的證明來自zhber 1、假設有這樣一個串12321，那么先合并兩個2一定比先合并兩個1更優

所以發現如果兩對元素的位置是嵌套關系的話先刪掉中間那對更優

2、假設又有123456712的串，要合并1、2，那么先合并1和先合并2是沒有區別的

所以發現如果兩對元素之間是有交集的話無論哪對先刪都一樣

3、顯然如果兩對元素之間沒有交集的話肯定互不影響

綜上，這樣的貪心是正確的。 然后兩個點的距離用BIT搞一下就好了。

解題方法2, 就是把上面的BIT換成棧或者線段樹來維護。