分数: 800 点
问题陈述
有 N 正整数 A_1, A_2, ..., A_N。 高桥可以对这些整数执行任意多次以下操作:
- 选择 1 \leq i \leq N 并乘以 A_i by -2.
请注意,他将其乘以 减 二。
他想做 A_1 \leq A_2 \leq ... \leq A_N 成立。
求出所需的最少操作次数。如果不可能,则打印 -1.
约束
- 1 \leq N \leq 200000
- 1 \leq A_i \leq 10^9
输入
输入由标准输入按以下格式给出:
N A_1 A_2 ... A_N
输出
打印答案。
示例输入 1
4 3 1 4 1
示例输出 1
3
一种可能的解决方案是:
- 选择 i=4 并乘以 A_4 by -2. A_1, A_2, A_3, A_4 现在 3, 1, 4, -2.
- 选择 i=1 并乘以 A_1 by -2. A_1, A_2, A_3, A_4 现在 -6, 1, 4, -2.
- 选择 i=4 并乘以 A_4 by -2. A_1, A_2, A_3, A_4 现在 -6, 1, 4, 4.
示例输入 2
5 1 2 3 4 5
示例输出 2
0
A_1 \leq A_2 \leq ... \leq A_N 在执行任何操作之前保持。
示例输入 3
8 657312726 129662684 181537270 324043958 468214806 916875077 825989291 319670097
示例输出 3
7