← 返回题目列表

AtCoder · arc139_a

A. 尾随零

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

对于正整数 x,让 \mathrm{ctz}(x) 是二进制表示中尾随零的数量 x.
例如,我们有 \mathrm{ctz}(8)=3 因为二进制表示 8 is 1000,和 \mathrm{ctz}(5)=0 因为二进制表示 5 is 101.

给你一个非负整数序列 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 正在严格增加。
  • \mathrm{ctz}(A_i) = T_i 对于每个整数都成立 i 这样 1 \leq i \leq N.

的最小可能值是多少 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位整数。


示例输入 4

8
2 0 2 2 0 4 2 4

示例输出 4

80