p03198 CADDi 2018 - Negative Doubling_5055
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.

Examples

Input

4
3 1 4 1


Output

3


Input

5
1 2 3 4 5


Output

0


Input

8
657312726 129662684 181537270 324043958 468214806 916875077 825989291 319670097


Output

7
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sqr(x) ((x)*(x))
#define mp make_pair
#define ld long double
#define PI pair<int,int>
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
const int N=200005;
int a[N],q[N],top,A[N];
ll f[N],g[N];
int cmp(ll a,ll b,int c){
	if(a>b){
		while(a>b){b<<=2; c+=2;}
		return c;
	}else{
		while(a<=b){a<<=2; c-=2;}
		return c+2;
	}
}
int main(){
	int n=read();
	for(int i=1;i<=n;i++)a[i]=read(); q[0]=n+1;
	ll dq=0;
	for(int i=n;i;i--){
		int t=0;
		while(top){
			int jb=cmp(a[q[top]-1],a[q[top]],t);
			if(jb>0){
				dq+=(ll)jb*(q[top-1]-q[top]); t=jb+A[top]; top--;
			}else break;
		}
		q[++top]=i; 
		A[top]=t;
		f[i]=dq;
	}
	dq=top=q[0]=0;
	for(int i=1;i<=n;i++){
		int t=0;
		a[i]*=2;
		while(top){
			int jb=cmp(a[q[top]+1],a[q[top]],t);
			if(jb>0){
				dq+=(ll)jb*(q[top]-q[top-1]); t=jb+A[top]; top--;
			}else break;
		}
		q[++top]=i; 
		A[top]=t;
		g[i]=dq;
		//cout<<g[i]<<" fjzzq "<<f[i]<<endl;
	}
	ll ans=1e18;
	for(int i=0;i<=n;i++){
		ans=min(ans,g[i]+f[i+1]+i);
	}
	cout<<ans<<endl;
}
