思路

从左向右处理数组。前面的结果已经确定时，当前数应该变为不小于前一个结果的最小倍增值。继续增大当前数只会增加操作次数，还会让后面更难满足条件，因此这样的贪心选择最优。

直接保存倍增后的整数可能需要非常多的二进制位。可以只记录每个原始数被乘以 $2$ 的次数。

做法

设上一个数需要乘以 $2$ 共 $q$ 次。令 $d$ 为满足

的最小整数，这里的 $d$ 可以为负数。

如果 $a_i<a_{i-1}$，不断将 $a_i$ 的临时副本乘以 $2$，直到不小于 $a_{i-1}$，倍增次数就是 $d$。

如果 $a_i\ge a_{i-1}$，不断将 $a_{i-1}$ 的临时副本乘以 $2$，只要结果仍不超过 $a_i$ 就继续；此时 $d$ 等于倍增次数的相反数。

于是当前数最少需要的操作次数为

把 $q'$ 加入答案，并用它更新状态。第一个数无需操作，初始状态为 $q=0$。

这里所有临时倍增都发生在两个原始数之间，整数最多增长到 $2\cdot10^9$，不需要真的构造原数组倍增后的巨大数值。最终操作总数可能超过32位整数范围，应使用64位整数。

正确性证明

对处理的前缀长度归纳。第一个数不做操作最优，因为增大它只会增加代价并加强后续限制。

假设已得到前一个位置的最小可行结果 $a_{i-1}2^q$。当前数操作 $k$ 次后的可行条件为

等价于 $k-q\ge d$。再结合操作次数不能为负，最小可行次数恰好是 $\max(0,q+d)$。

任何其他可行前缀都不可能在前一个位置得到更小的结果，因此也不能让当前位置使用更少操作。选取当前最小结果同样不会增加后续限制。归纳成立，累加得到的操作总数最小。

部分分做法

子任务1可以枚举各个位置的操作次数并检查结果。设 $M=\max a_i$，存在最优解使每项操作次数不超过 $n-1+\lfloor\log_2 M\rfloor$，因此搜索域有限。

子任务2使用大整数，按贪心策略逐次把当前值乘以 $2$。它正确地模拟原操作，但操作总次数以及整数位数都可能随数组长度增长。

子任务3将操作次数作为状态。设 $f_q$ 是前一个数操作 $q$ 次时的最小前缀代价，当前操作 $k$ 次时，前一指数满足 $q\le k-d$。利用 $f$ 的前缀最小值完成转移即可，避免逐次操作实际大整数。指数上界来自：每处理一个位置，最终二进制长度最多在已有长度基础上增加一位，原始位数不超过 $\lfloor\log_2 M\rfloor+1$。

复杂度

完整算法的时间复杂度为 $O(n\log M)$，每次原始整数比较最多进行30次倍增。所有测试的总长度不超过 $2\cdot10^5$。额外递推状态占 $O(1)$ 空间；保存输入数组的实现占 $O(n)$ 总空间。

指数状态动态规划需要 $O(n(n+\log M))$ 时间和 $O(n+\log M)$ 状态空间。大整数逐次模拟还需承担每次倍增时的多字运算代价，最坏可达到关于 $n$ 的三次量级；极小层的指数枚举为指数复杂度。