题目描述

正の整数 $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$ としてあり得る値の最小値を答えてください。

输入格式

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

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

输出格式

答えを出力せよ。

4
0 1 3 2

12

5
4 3 2 1 0

31

1
40

1099511627776

8
2 0 2 2 0 4 2 4

80

提示

制約

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

Sample Explanation 1

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

Sample Explanation 3

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