第 1 题 两倍 (double)

时间限制 1.0 s · 空间限制 256 MB · 74 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 double.in，输出文件 double.out。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

给定一个长度为 $N$ 的正整数序列 $A_1, A_2, \dots, A_N$。现在希望将该序列变为升序排列。所谓升序排列，是指对于所有的 $i$（$1 \le i \le N - 1$），都有 $A_i \le A_{i+1}$。

为了将序列 $A$ 排成升序，可以对序列执行以下操作若干次（可为零次）：

• 对于某个 $i$（$1 \le i \le N$），将 $A_i$ 乘以 $2$。

你的任务是以最小的操作次数将序列 $A$ 排成升序，并输出所需的最小操作次数。

输入格式

第一行输入一个整数 $N$。

第二行输入 $N$ 个整数，表示 $A_1, A_2, \dots, A_N$，以空格分隔。

输出格式

输出一个整数，表示将序列变为升序所需的最小操作次数。

样例

样例 1

输入：

5
3 1 4 1 5

输出：

4

样例 2

输入：

5
3 1 5 1 5

输出：

6

样例 3

输入：

5
1 2 3 4 5

输出：

0

提示

样例 1 说明

对 $A_2$ 和 $A_4$ 各执行两次操作后，序列变为 $[3, 4, 4, 4, 5]$。

样例 2 说明

对 $A_2$ 操作两次，$A_4$ 操作三次，$A_5$ 操作一次，最终序列为 $[3, 4, 5, 8, 10]$。

数据范围

约束条件

• 所有给定的数均为整数。
• $1 \le N \le 250\,000$
• $1 \le A_i \le 1\,000\,000$，其中 $1 \le i \le N$

子问题

1. （12 分）对于所有 $i$（$1 \le i \le N$），$A_i = 1$ 或 $A_i = 2$
2. （10 分）对于所有 $i$（$1 \le i \le N$），存在非负整数 $k_i$，使得 $A_i = 2^{k_i}$
3. （11 分）$N \le 10$
4. （19 分）对于所有 $i$（$1 \le i \le N$），$A_i = 2$ 或 $A_i = 3$
5. （20 分）对于所有 $i$（$1 \le i \le N - 1$），$A_i \ge A_{i+1}$
6. （28 分）无额外限制条件

翻译由 ChatGPT-4o 完成