/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
N 個の正の整数 A_1, A_2, ..., A_N があります． 高橋君は，これらの整数に対して，次の操作を好きな回数行うことができます：
- 1 \leq i \leq N を選び，A_i の値を -2 倍にする．
マイナス 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 の値を -2 倍にする．A_1, A_2, A_3, A_4 はそれぞれ 3, 1, 4, -2 になる．
- i=1 を選び，A_1 の値を -2 倍にする．A_1, A_2, A_3, A_4 はそれぞれ -6, 1, 4, -2 になる．
- i=4 を選び，A_4 の値を -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
Score : 800 points
Problem Statement
There are N positive integers A_1, A_2, ..., A_N. Takahashi can perform the following operation on these integers any number of times:
- Choose 1 \leq i \leq N and multiply the value of A_i by -2.
Notice that he multiplies it by minus two.
He would like to make A_1 \leq A_2 \leq ... \leq A_N holds.
Find the minimum number of operations required. If it is impossible, print -1.
Constraints
- 1 \leq N \leq 200000
- 1 \leq A_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N A_1 A_2 ... A_N
Output
Print the answer.
Sample Input 1
4 3 1 4 1
Sample Output 1
3
One possible solution is:
- Choose i=4 and multiply the value of A_4 by -2. A_1, A_2, A_3, A_4 are now 3, 1, 4, -2.
- Choose i=1 and multiply the value of A_1 by -2. A_1, A_2, A_3, A_4 are now -6, 1, 4, -2.
- Choose i=4 and multiply the value of A_4 by -2. A_1, A_2, A_3, A_4 are now -6, 1, 4, 4.
Sample Input 2
5 1 2 3 4 5
Sample Output 2
0
A_1 \leq A_2 \leq ... \leq A_N holds before any operation is performed.
Sample Input 3
8 657312726 129662684 181537270 324043958 468214806 916875077 825989291 319670097
Sample Output 3
7