思路

根据题意，我们只需要考虑每个偶数段。 问题简化为：找到每个偶数段，找到这个偶数段中，和最小的一个子区间，然后将这个子区间的值减半即可。 那么这就是一个最大子数组和的问题，只不过这里要求的是最小子数组和。 我们依旧可以按照最大子数组和的模板来解决这道题。

题目描述

小红除2拿到了一个数组，她可以进行最多一次操作:选择一个元素全是偶数的区间，使这个区间所有元素除以2。

小红除2希望最终所有元素之和尽可能大，你能帮帮她吗?

输入描述

第一行输入一个正整数$n$代表数组的大小。

第二行输入$n$个正整数$a_i$:代表数组的元素。 $1\le n\le 10^5$

$-10^9\le a_i\le 10^9$

输出描述

一个整数，代表最终所有元素之和的最大值。

样例

输入

5
8 -4 2 -6 -5

输出

-1

说明

选择区间[-4,2,-6]即可，操作后数组变成[8,-2,1,-3,-5]