← 返回题目列表

AtCoder · caddi2018_c

E. 负倍增

中文机器翻译题面 查看原题

分数: 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