题目背景

Special for beginners, ^_^

题目描述

有 n 个数排成一排，记为：

a1 a2 ... an

现在进行 n 次操作，第 i 次操作如下：

如果 ai 是 偶数，则把 ai / 2 加到 ai+1 上。 如果 ai 是 奇数，则把 ai 加到 ai+1 上。

注意：

操作是 按顺序执行 的

修改会影响后面的操作

第 n 个数的操作不会影响任何位置

所有操作完成后，输出 数组中最大的数。

输入格式

第一行输入一个整数 n。

第二行输入 n 个整数：

a1 a2 ... an

数据范围：

1 ≤ n ≤ 2e5 0 ≤ ai ≤ 1e9

输出格式

输出一个整数，表示最终数组中的最大值。

样例

5
2 3 4 5 6

10

样例解释

初始：

2 3 4 5 6

操作1：2 是偶数 → 2/2 = 1 加到 a2

2 4 4 5 6

操作2：4 是偶数 → 4/2 = 2 加到 a3

2 4 6 5 6

操作3：6 是偶数 → 6/2 = 3 加到 a4

2 4 6 8 6

操作4：8 是偶数 → 8/2 = 4 加到 a5

2 4 6 8 10

最大值：

10