https://codeforces.com/contest/2035/problem/D
首先显然这个函数很实用，处理出一个数因子2的个数，和剩下的数（姑且称作left数）。

pair<ll,ll> get_2_factor(ll x){
    ll t = 0;
    while(x%2==0){
        x/=2,t++;
    }
    return {t,x};
}

根据样例2
11
1 6 9 4 7 4 4 10 3 2 3
需要手动模拟然后找出一个贪心规律：
[1]、[1,6]、[1,3,2*9]、[1,3,2*9,4]、[1,3,9,1,7*4*2]、[1,3,9,1,7*4*2,4]…

因此发现都是一个个$“all\_in”$段构成的（指把这一段里的所有2，都$all\_in$到这段的最后一个数，ps.一个数也是一个”all_in段”）。
因此dp[i]的集合就是在前面找一个分界点j，左边答案是dp[j]，右边是这一段所有的2，$all_in$到$a[i]$上。但是这样是TLE的，应该有某种方法快速找到能更新$dp[i]$的地方。
考虑相邻的两个段，如果把前一个段的2 $all\_in$到下一个段（或者说合并这两个段），需要满足什么条件才能使得合并之后$ans$更大呢：很容易发现，如果前面那一个段的最后一个数的$left数$小于等于后一个段的$a[i]$（这里的$a[i]$是被$all\_in$过的$a[i]$），那么就可以合并这一段。再贪心一下，$dp[i]$就是从i位置一直往前合并的过程，合并的条件是$a[i]$大于等于$a[j]（j<i）$。
于是问题转换成找到最大的j，使得$a[i]$乘以$j+1$到$i-1$段所有的2之后，仍然小于$a[j]$的$left数$。然后答案就是$ans[j]$加上$a[i]$乘以$j+1$到$i-1$段所有的2，再加上$j+1$到$i-1$段所有的$left数$。

单调栈可以使得这个查找过程变成O(n)。理由是每个点最多进栈一次出栈一次。

于是算法流程变为：
0.处理2的个数和$left数$的前缀和
1.到达$i$位置，一直出栈，直到空或者找到$j$使得$a[j]$的$left数$/$a[i]$小于等于$j+1$到$i-1$段所有的2相乘（防止溢出mod）。若空，答案为把所有的2 $all_in$到$a[i]$，再加上1到i-1段的$left数$和。
2.若不空，$ans[i]=ans[j]加上a[i]乘以j+1到i-1段所有的2，再加上j+1到i-1段所有的left数。$