問題描述

Alice是一個讓人非常愉躍的人!他總是去學(xué)習(xí)一些他不懂的問題，然后再想出許多稀奇古怪的題目。這幾天，Alice又沉浸在逆序?qū)Φ目鞓樊?dāng)中，他已近學(xué)會了如何求逆序?qū)?shù)，動態(tài)維護(hù)逆序?qū)?shù)等等題目，他認(rèn)為把這些題讓你做簡直是太沒追求了，于是，經(jīng)過一天的思考和完善，Alice終于拿出了一道他認(rèn)為差不多的題目：

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

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

輸入格式

第一行一個整數(shù)n。

下面每行，一個數(shù)x。

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

輸出格式

輸出一個整數(shù)，表示最少有多少逆序?qū)Α?/span>

樣例輸入

3

0

0

3

1

2

樣例輸出

1

數(shù)據(jù)規(guī)模與約定

對于20%的數(shù)據(jù)，n <= 5000。

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