题目描述

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

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

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

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

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

5
3 1 4 1 5

输出 #1

4

输入输出样例 #2

输入 #2

5
3 1 5 1 5

输出 #2

6

输入输出样例 #3

输入 #3

5
1 2 3 4 5

输出 #3

0

说明/提示

样例 1 说明

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

样例 2 说明

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

约束条件

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

子问题

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

翻译由 ChatGPT-4o 完成