分数: 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