配点 : $300$ 点

問題文

正の整数 $x$ に対して、 $x$ を $2$ 進表記したときの末尾に連なる $0$ の個数を $\mathrm{ctz}(x)$ と定めます。 たとえば $8$ の $2$ 進表記は 1000 なので $\mathrm{ctz}(8)=3$ で、$5$ の $2$ 進表記は 101 なので $\mathrm{ctz}(5)=0$ です。

非負整数からなる数列 $T = (T_1,T_2,\dots,T_N)$ が与えられます。 正の整数からなる数列 $A = (A_1,A_2,\dots,A_N)$ を以下の条件を満たすように自由に構成します。

• $A_1 \lt A_2 \lt \cdots \lt A_{N-1} \lt A_N$ である。すなわち $A$ は狭義単調増加である。
• $1 \leq i \leq N$ を満たす全ての整数 $i$ に対して $\mathrm{ctz}(A_i) = T_i$ が成り立つ。

このとき $A_N$ としてあり得る値の最小値を答えてください。

制約

• $1 \leq N \leq 10^5$
• $0 \leq T_i \leq 40$
• 入力される値はすべて整数

入力

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

$N$

$T_1$ $T_2$ $\dots$ $T_N$

出力

答えを出力せよ。

4
0 1 3 2

12

たとえば $A_1=3,A_2=6,A_3=8,A_4=12$ は条件を満たします。 $A_4$ を $11$ 以下にすることはできないので答えは $12$ になります。

5
4 3 2 1 0

31

1
40

1099511627776

答えが $32$ bit 整数に収まらない場合があるのに注意してください。

8
2 0 2 2 0 4 2 4

80