AT_arc139_a [ARC139A] Trailing Zeros

题目描述

对于正整数 $x$，我们定义 $x$ 的二进制表示中末尾连续的零的个数为 $\mathrm{ctz}(x)$。

例如，$8$ 的二进制表示为 1000，所以 $\mathrm{ctz}(8)=3$；$5$ 的二进制表示为 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$

输出格式

输出答案。

样例 1

输入

4
0 1 3 2

输出

12

样例 2

输入

5
4 3 2 1 0

输出

31

样例 3

输入

1
40

输出

1099511627776

样例 4

输入

8
2 0 2 2 0 4 2 4

输出

80

说明/提示

• $1\ \leq\ N\ \leq\ 10^5$
• $0\ \leq\ T_i\ \leq\ 40$
• 输入的所有值都是整数

【样例解释 1】

例如，$A_1=3,A_2=6,A_3=8,A_4=12$ 满足条件。由于 $A_4$ 不能小于 $11$，所以答案为 $12$。

【样例解释 3】

注意答案可能不适合 $32$ 位整数。