A - Trailing Zeros Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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

出力

答えを出力せよ。

入力例 1

4
0 1 3 2

出力例 1

12

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

入力例 2

5
4 3 2 1 0

出力例 2

31

入力例 3

1
40

出力例 3

1099511627776

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

入力例 4

8
2 0 2 2 0 4 2 4

出力例 4

80

Score : 300 points

Problem Statement

For a positive integer x, let \mathrm{ctz}(x) be the number of trailing zeros in the binary representation of x.
For example, we have \mathrm{ctz}(8)=3 because the binary representation of 8 is 1000, and \mathrm{ctz}(5)=0 because the binary representation of 5 is 101.

You are given a sequence of non-negative integers T = (T_1,T_2,\dots,T_N).
Consider making a sequence of positive integers A = (A_1, A_2, \dots, A_N) of your choice so that it satisfies the following conditions.

  • A_1 \lt A_2 \lt \cdots \lt A_{N-1} \lt A_N holds. In other words, A is strictly increasing.
  • \mathrm{ctz}(A_i) = T_i holds for every integer i such that 1 \leq i \leq N.

What is the minimum possible value of A_N here?

Constraints

  • 1 \leq N \leq 10^5
  • 0 \leq T_i \leq 40
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
T_1 T_2 \dots T_N

Output

Print the answer.

Sample Input 1

4
0 1 3 2

Sample Output 1

12

For example, A_1=3,A_2=6,A_3=8,A_4=12 satisfy the conditions.
A_4 cannot be 11 or less, so the answer is 12.

Sample Input 2

5
4 3 2 1 0

Sample Output 2

31

Sample Input 3

1
40

Sample Output 3

1099511627776

Note that the answer may not fit into a 32-bit integer.

Sample Input 4

8
2 0 2 2 0 4 2 4

Sample Output 4

80