問(wèn)題描述

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

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

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

輸入格式

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

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

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

輸出格式

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

樣例輸入

3

0

0

3

1

2

樣例輸出

1

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

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

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