問題描述

Alice是一個讓人非常愉躍的人!他總是去學習一些他不懂的問題，然后再想出許多稀奇古怪的題目。這幾天，Alice又沉浸在逆序對的快樂當中，他已近學會了如何求逆序對對數，動態維護逆序對對數等等題目，他認為把這些題讓你做簡直是太沒追求了，于是，經過一天的思考和完善，Alice終于拿出了一道他認為差不多的題目：

有一顆2n-1個節點的二叉樹，它有恰好n個葉子節點，每個節點上寫了一個整數。如果將這棵樹的所有葉子節點上的數從左到右寫下來，便得到一個序列a[1]…a[n]。現在想讓這個序列中的逆序對數量最少，但唯一的操作就是選樹上一個非葉子節點，將它的左右兩顆子樹交換。他可以做任意多次這個操作。求在最優方案下，該序列的逆序對數最少有多少。

Alice自己已近想出了題目的正解，他打算拿來和你分享，他要求你在最短的時間內完成。

輸入格式

第一行一個整數n。

下面每行，一個數x。

如果x=0，表示這個節點非葉子節點，遞歸地向下讀入其左孩子和右孩子的信息，如果x≠0，表示這個節點是葉子節點，權值為x。

輸出格式

輸出一個整數，表示最少有多少逆序對。

樣例輸入

3

0

0

3

1

2

樣例輸出

1

數據規模與約定

對于20%的數據，n <= 5000。

對于100%的數據，1 <= n <= 200000，0 <= a[i]<2^31。