Problem 8C. 最少操作次数

题目描述

给你一个整数数组 \(a_1,a_2,…,a_n\)，你需要用最少的操作次数使数组不递减。在一次操作中，您需要执行以下操作：

• 选取一个下标 \(1 \le i \le n\)，
• 让 \(a_i = a_i * 2\).

如果一个数组 \(b_1, b_2, ..., b_n\)是非递减数组，那么对于每个下标 \(1 \le i < n\) 都满足 \(b_i \le b_{i+1}\)。

输入格式

第一行一个整数 \(n\) ，代表数组大小。

第二行 \(n\) 个整数 \(a_1, a_2, ..., a_n\)，代表数组中的每个数。

输出格式

输出一个整数，表示使数组变成非递减数组的最少操作次数。

样例输入

3
3 2 1

样例输出

3

样例解释

操作三次：

选择下标 \(i=3\)，数组变为\([3,2,2]\);

选择下标 \(i=3\)，数组变为\([3,2,4]\);

选择下标 \(i=2\)，数组变为\([3,4,4]\);

数据范围与约定

对于 \(60\%\) 的数据，\(1 \le n \le 20\), \(1 \le a_i \le 2^{10}\);

对于 \(100\%\) 的数据，\(1 \le n \le 10^5\), \(1 \le a_i \le 10^9\).