問題文

$N$ 個のマスが横一列に並んだマス目があります。左から $i$ 個目のマスをマス $i$ と呼びます。初期状態ではマス $i$ は $A_i=1$ ならば輝いていて、$A_i=0$ ならば輝いていません。

あなたはこれからいずれかのマスにロボットを置きます。置かれたロボットは以下の一連の動作を繰り返し行います。

1. 今いるマスがマス $N$ であるか輝いていない場合は動作を停止する。
2. $1$ つ右のマスに移動した後、全てのマスの「輝いている」「輝いていない」の状態を反転する。

それぞれのマスについてロボットをそのマスに置いた場合にロボットが移動する回数を求め、それらの総和を答えてください。

入力

$N$
$A_1$ $A_2$ $\dots$ $A_N$

• 入力はすべて整数
• $1 \le N \le 2 \times 10^5$
• $0 \le A_i \le 1$

出力

ロボットが移動する回数の総和を出力し、最後に改行してください。

サンプル

5
1 1 1 0 1

4

8
0 1 0 1 1 0 0 1

6

15
0 0 0 1 1 0 0 0 1 0 1 0 0 1 1

10