配点 : $1600$ 点

問題文

$A$ 匹のスライムが横一列に並んでいます。 最初、スライムの大きさはすべて $1$ です。

すぬけ君は次の操作を繰り返し行うことができます。

• 正の偶数 $M$ をひとつ選ぶ。 位置が連続する $M$ 匹のスライムを選び、それらのうち左から $(1,\ 2)$ 番目、$(3,\ 4)$ 番目、…、$(M - 1,\ M)$ 番目のスライムをそれぞれペアにする。 そして、各ペアごとに $2$ 匹のスライムを合成して $1$ 匹のスライムにする。 ここで、合成後のスライムの大きさは、合成前のスライムの大きさの和とする。 また、合成後の $M / 2$ 匹のスライムの順序は、合成前の $M / 2$ 組のペアの順序のままである。

すぬけ君の目標は、スライムをちょうど $N$ 匹にして、それらのうち左から $i$ ($1 \leq i \leq N$) 番目のスライムの大きさをちょうど $a_i$ にすることです。 すぬけ君が目標を達成するために必要な操作回数の最小値を求めてください。

なお、$A$ は入力として与えられず、$A = a_1 + a_2 + ... + a_N$ であるとします。

制約

• $1 \leq N \leq 10^5$
• $a_i$ は整数である。
• $1 \leq a_i \leq 10^9$

入力

入力は以下の形式で標準入力から与えられる。

$N$

$a_1$ $a_2$ $...$ $a_N$

出力

すぬけ君が目標を達成するために必要な操作回数の最小値を出力せよ。

2
3 3

2

次のように操作を行えばよいです。 操作対象のスライムを太字で表しています。

• (1, 1, 1, 1, 1, 1) → (1, 2, 2, 1)
• (1, 2, 2, 1) → (3, 3)

4
2 1 2 2

2

次のように操作を行えばよいです。

• (1, 1, 1, 1, 1, 1, 1) → (2, 1, 1, 1, 1, 1)
• (2, 1, 1, 1, 1, 1) → (2, 1, 2, 2)

1
1

0

10
3 1 4 1 5 9 2 6 5 3

10