Problem:
 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

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
def sub(a, minus=False):
    m = 20
    inf = 10**15
    dp = [[inf]*m for _ in range(n)] 
    for j in range(m):
        dp[-1][j] = j
    for i in range(n-2, -1, -1):
        if a[i]>a[i+1]:
            v = 0
            ai = a[i]; ai1 = a[i+1]
            while ai>ai1:
                ai1 *= 4
                v += 1
            for j in range(m):
                if j+v<m:
                    dp[i][j] = j + dp[i+1][j+v]
                else:
                    dp[i][j] = j + dp[i+1][m-1] + (n-i-1)*(j+v-m+1)
        else:
            v = 0
            ai = a[i]; ai1 = a[i+1]
            while True:
                ai *= 4
                if ai<=ai1:
                    v += 1
                else:
                    break
            for j in range(m):
                dp[i][j] = j + dp[i+1][max(0, j-v)]
    if minus:
        ans = [(2*min(dp[i][j] for j in range(m))+(n-i)) for i in range(n)]
    else:
        ans = [2*min(dp[i][j] for j in range(m)) for i in range(n)]
    return ans
dp0 = sub(list(a))
dp1 = sub([item for item in a[::-1]], minus=True)[::-1]
dp0.append(0)
dp1.insert(0,0)
ans = min((dp0[i]+dp1[i]) for i in range(n+1))
print(ans)

Solution (Python):
from collections import deque

n = int(input())
a = list(map(int,input().split()))

p = [0] * (n-1)
m = [0] * (n-1)

for i in range(n-1):
    x,y = a[i:i+2]
    cnt = 0
    if(x > y):
        while(x>y):
            y *= 4
            cnt += 2
    else:
        x *= 4
        while(x<=y):
            x*=4
            cnt -= 2
    p[i] = cnt

for i in range(n-1):
    x,y = a[i:i+2]
    cnt = 0
    if(x < y):
        while(x<y):
            x *= 4
            cnt += 2
    else:
        y *= 4
        while(x>=y):
            y*=4
            cnt -= 2
    m[i] = cnt

cumsum_p = [0] * (n+1)
cumsum_m = [0] * (n+1)

d = deque()
for i in range(n-2,-1,-1):
    cumsum_p[i] = cumsum_p[i+1]
    if(p[i] < 0):
        d.appendleft((i,p[i]))
    elif(p[i] > 0):
        cnt = p[i]
        while(d):
            j,rem_j = d.popleft()
            if(cnt + rem_j <= 0):
                cumsum_p[i] += (j-i) * cnt
                if(cnt + rem_j < 0):
                    d.appendleft((j,cnt + rem_j))
                cnt = 0
                break
            else:
                cumsum_p[i] += (j-i) * (-1 * rem_j)
                cnt = cnt + rem_j
        cumsum_p[i] += (n-i-1) * cnt

d = deque()
cumsum_m[1] = 1
for i in range(n-1):
    cumsum_m[i+2] = cumsum_m[i+1] + 1
    if(m[i] < 0):
        d.appendleft((i,m[i]))
    elif(m[i] > 0):
        cnt = m[i]
        while(d):
            j,rem_j = d.popleft()
            if( cnt + rem_j <= 0 ):
                cumsum_m[i+2] += (i-j) * cnt
                if( cnt + rem_j < 0):
                    d.appendleft((j,cnt + rem_j))
                cnt = 0
                break
            else:
                cumsum_m[i+2] += (i-j) * (-1*rem_j)
                cnt = cnt + rem_j
        cumsum_m[i+2] += (i+1) * cnt

ans = cumsum_p[0]
for i in range(n+1):
    ans = min(ans, cumsum_p[i] + cumsum_m[i])

print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
def d4(x,y):
  ret = 0
  while x > y:
    y *= 4
    ret += 1
  return ret
def cost(ls):
  l = len(ls)
  ret = [0]*l
  stack = [(l-1,10**18)]
  for i in range(l-1)[::-1]:
    ret[i] = ret[i+1]
    if ls[i] <= ls[i+1]:
      d = d4(ls[i+1],ls[i])-1
      if d > 0:
        stack.append((i,d))
    else:
      d = d4(ls[i],ls[i+1])
      while d:
        idx,num = stack.pop()
        if d > num:
          ret[i] += (idx-i)*num
          d -= num
        else:
          ret[i] += (idx-i)*d
          num -= d
          d = 0
          if num:
            stack.append((idx,num))
  return ret
cp = cost(a)
cn = cost(a[::-1])
for i in range(n):
  cp[i] *= 2
  cn[i] *= 2
  cn[i] += n-i
ansls = [cp[0],cn[0]]
for i in range(1,n):
  ansls.append(cp[i]+cn[n-i])
print(min(ansls))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
b = list(reversed(a))
c = [0] * (n + 1)
d = [0] * (n + 1)
s = [(0, 10 ** 30)]
res = 0
for i in range(1, n):
    if a[i - 1] < a[i] * 4:
        t = a[i - 1]
        cnt = 0
        while t < a[i]:
            cnt += 1
            t *= 4
        while cnt > 0:
            idx, p = s.pop()
            if cnt >= p:
                res += p * (i - idx)
                cnt -= p
            else:
                res += cnt * (i - idx)
                s.append((idx, p - cnt))
                cnt = 0
    else:
        t = a[i]
        cnt = 0
        while a[i - 1] >= t * 4:
            t *= 4
            cnt += 1
        s.append((i, cnt))
    c[i + 1] = res
s = [(0, 10 ** 30)]
res = 0
for i in range(1, n):
    if b[i - 1] < b[i] * 4:
        t = b[i - 1]
        cnt = 0
        while t < b[i]:
            cnt += 1
            t *= 4
        while cnt > 0:
            idx, p = s.pop()
            if cnt >= p:
                res += p * (i - idx)
                cnt -= p
            else:
                res += cnt * (i - idx)
                s.append((idx, p - cnt))
                cnt = 0
    else:
        t = b[i]
        cnt = 0
        while b[i - 1] >= t * 4:
            t *= 4
            cnt += 1
        s.append((i, cnt))
    d[i + 1] = res
ans = float('inf')
for i in range(n + 1):
    ans = min(ans, (c[i] + d[n - i]) * 2 + i)
print(ans)

Solution (Python):
class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = ide_ele
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.tree[self.num + i] = i
        
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

def main():
    import random
    from math import log,ceil

    N=int(input())
    n=N

    A=list(map(int,input().split()))
    A=[log(A[i],4) for i in range(N)]
    B=[A[-i-1] for i in range(N)]
    memo=[0]*(N-1)
    ans=10**25
    ope=[0 for i in range(N+1)]
    ope[N]=10**20

    def segfunc(x,y):
        if ope[x]>ope[y]:
            return y
        elif ope[y]>ope[x]:
            return x
        else:
            return min(x,y)
    
    ide_ele = N
    


    for i in range(1,N):
        ope[i]=max(0,ceil(A[i-1]-A[i]))
        A[i]+=ope[i]

    rmq=SegTree(segfunc,ide_ele)

    S=sum(ope[i] for i in range(N))
    ans=min(ans,2*S)
    zero=[N]

    
    BIT = [0]*(n+1)
    
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(1,N):
        while i!=zero[-1]:
            k=rmq.query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[i-1]+=2*S

    ope=[0 for i in range(N+1)]
    ope[N]=10**20
    S=0
    for i in range(1,N):
        ope[i]=max(0,ceil(B[i-1]-B[i]))
        S+=ope[i]
        B[i]+=ope[i]
    
    rmq=SegTree(segfunc,ide_ele)
    

    ans=min(ans,2*S+N)
    zero=[N]
    BIT=[0]*(n+1)

    for i in range(1,N):
        while i!=zero[-1]:
            k=rmq.query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[N-1-i]+=2*S+(N-i)
    
    test=min(memo)
    print(min(test,ans))

if __name__=="__main__":
    main()

Solution (Python):
INF = 10**10
n = int(input())
a = list(map(int, input().split()))

dp_fr = [[INF for _ in range(20)] for _ in range(n)]
dp_ba = [[INF for _ in range(20)] for _ in range(n)]


for j in range(20):
	dp_fr[0][j] = 2*j

for i in range(1, n):
	if a[i-1] < a[i]:
		k = 0
		while a[i-1] * pow(4, k) < a[i]:
			k += 1
		for j in range(20):
			if j+k < 20:
				dp_fr[i][j] = 2*j + dp_fr[i-1][j+k]
			else:
				dp_fr[i][j] = 2*j + dp_fr[i-1][19] + 2*(i) * (j+k-19)
	else:
		k = 0
		while a[i-1] >= a[i] * pow(4, k+1):
			k += 1
		for j in range(20):
			dp_fr[i][j] = 2*j + dp_fr[i-1][max(j-k, 0)]

for j in range(20):
	dp_ba[n-1][j] = 2*j

for i in range(n-2, -1, -1):
	if a[i+1] < a[i]:
		k = 0
		while a[i+1] * pow(4, k) < a[i]:
			k += 1
		for j in range(20):
			if j+k < 20:
				dp_ba[i][j] = 2*j + dp_ba[i+1][j+k]
			else:
				dp_ba[i][j] = 2*j + dp_ba[i+1][19] + 2*(n-i-1) * (j+k-19)
	else:
		k = 0
		while a[i+1] >= a[i] * pow(4, k+1):
			k += 1
		for j in range(20):
			dp_ba[i][j] = 2*j + dp_ba[i+1][max(j-k, 0)]




ans = min(dp_ba[0][0], n + dp_fr[n-1][0])
for i in range(n-1):
	ans = min(ans, dp_ba[i+1][0] + i+1 + dp_fr[i][0])

print(ans)

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    def f(a, b):
        ret = 0
        while a > b:
            ret += 2
            b *= 4
        return ret

    N = int(input())
    A = list(map(int, input().split()))

    right = [0] * (N+1)
    st = [(1, A[-1], A[-1])]
    for i in range(N-2, -1, -1):
        a = A[i]
        st.append((1, a, a))
        right[i] = right[i+1]
        while True:
            if len(st) == 1:
                break
            if st[-1][2] > st[-2][1]:
                na, amin, amax = st.pop()
                nb, bmin, bmax = st.pop()
                k = f(amax, bmin)
                right[i] += nb * k
                if st:
                    st.append((na+nb, amin, bmax << k))
                else:
                    st.append((na+nb, amin, float("inf")))
            else:
                break
    left = [0] * (N+1)
    left[1] = 1
    st = [(1, A[0], A[0])]
    for i in range(2, N+1):
        a = A[i-1]
        st.append((1, a, a))
        left[i] = left[i-1] + 1
        while True:
            if len(st) == 1:
                break
            if st[-1][2] > st[-2][1]:
                na, amin, amax = st.pop()
                nb, bmin, bmax = st.pop()
                k = f(amax, bmin)
                left[i] += nb * k
                if st:
                    st.append((na + nb, amin, bmax << k))
                else:
                    st.append((na+nb, amin, float("inf")))
            else:
                break
    ans = float("inf")
    for i in range(N+1):
        ans = min(ans, left[i] + right[i])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np


def calc_mul4_dp(n, aaa):
    

    
    
    
    
    stack = [(10 ** 12, 10 ** 12, n), (aaa[-1], aaa[-1], n - 1)]
    INF = 10 ** 11
    result = [0, 0]

    for i in range(n - 2, -1, -1):
        a = aaa[i]
        c = a
        inc = 0
        while (c << 2) > stack[-1][0]:
            b, e, j = stack.pop()
            mul = 0
            while c > b:
                b <<= 2
                mul += 1
            inc += mul * (stack[-1][2] - j)
            c = min(e << (2 * mul), INF)
        stack.append((a, c, i))
        result.append(inc)
        
    result = np.add.accumulate(result, dtype=np.int64)[::-1]
    return result


def solve(n, aaa):
    fdp = calc_mul4_dp(n, aaa)
    bdp = calc_mul4_dp(n, aaa[::-1])[::-1]
    
    
    return ((fdp + bdp) * 2 + np.arange(n + 1, dtype=np.int64)).min()


def test():
    import random
    n = 200000
    
    
    aaa = list(range(10 ** 9, 10 ** 9 - n, -1))
    print(n)
    
    print(solve(n, aaa))




n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Solution (Python):
import numpy as np


def calc_mul4_dp(n, aaa):
    

    
    
    
    stack = [(10 ** 20, 10 ** 20, n), (aaa[-1], aaa[-1], n - 1)]
    INF = 10 ** 19
    result = [0, 0]

    for i in range(n - 2, -1, -1):
        a = aaa[i]
        c = a
        inc = 0
        while (c << 2) > stack[-1][0]:
            b, e, j = stack.pop()
            mul = 0
            while c > b:
                b <<= 2
                mul += 1
            inc += mul * (stack[-1][2] - j)
            c = min(e << (2 * mul), INF)
        stack.append((a, c, i))
        result.append(inc)
        
    result = np.add.accumulate(result, dtype=np.int64)[::-1]
    return result


def solve(n, aaa):
    fdp = calc_mul4_dp(n, aaa)
    bdp = calc_mul4_dp(n, aaa[::-1])[::-1]
    
    
    return ((fdp + bdp) * 2 + np.arange(n + 1, dtype=np.int64)).min()


def test():
    import random
    n = 200000
    
    
    aaa = list(range(10 ** 9, 10 ** 9 - n, -1))
    print(n)
    
    print(solve(n, aaa))




n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Solution (Python):
import sys
readline = sys.stdin.readline

def f(a, b):
    return (1+(-(-a//b)-1).bit_length())//2

N = int(readline())
A = list(map(int, readline().split()))

dpr = [0]*N
Ar = A[:]
cnt = 0
for i in range(1, N):
    res = 0
    idx = i-1
    while cnt <= idx:
        k = f(Ar[idx+1], Ar[idx])
        if k:
            Ar[idx] *= 4**k
            res += k
        idx -= 1
        if not k:
            break
    else:
        dpr[i] += cnt*k
    dpr[i] += dpr[i-1] + res
    while cnt < i:
        if Ar[cnt] < Ar[cnt+1]*4:
            cnt += 1
        else:
            break

dpl = [0]*N
Al = A[:]
cnt = N-1
for i in range(N-2, -1, -1):
    res = 0
    idx = i+1
    while cnt >= idx:
        k = f(Al[idx-1], Al[idx])
        if k:
            Al[idx] *= 4**k
            res += k
        idx += 1
        if not k:
            break
    else:
        dpl[i] += (N-1-cnt)*k
    dpl[i] += dpl[i+1] + res
    while cnt > i:
        if Al[cnt] < Al[cnt-1]*4:
            cnt -= 1
        else:
            break
dpl = [2*dpl[i] for i in range(N)]
dpr = [0] + [i+1+2*dpr[i] for i in range(N)]
inf = 10**20
ans = inf
for i in range(N):
    ans = min(ans, dpr[i] + dpl[i])
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・正、負の部分に分けて。本質的には正の場合ができればよい
・4A_i > A_{i+1} となってるものはまとめる。運命共同体の区間たちができる
・一番弱い区間と勝負する。成長すると次の区間とマージできる
"""

N,*A = map(int,read().split())

def calc_positive_case(N,A):
    INF = 1<<32
    
    dp = [0] * N
    left_end = []
    right_end = []
    items = []
    mult_cnt = 0
    for i,x in enumerate(A[::-1]):
        left_end.append(x); right_end.append(x); items.append(1)
        
        while len(items) >= 2:
            l2,l1 = left_end[-2:]
            r2,r1 = right_end[-2:]
            n2,n1 = items[-2:]
            if r1*4<=l2:
                
                break
            while r1>l2:
                l2 *= 4; r2 *= 4; mult_cnt += n2
            left_end.pop(); left_end[-1]=l1
            right_end.pop(); right_end[-1]=r2
            items.pop(); items[-1] += n1
        if right_end[0] > INF:
            right_end[0] = INF
        dp[i] = mult_cnt
    return dp[::-1]

pos = calc_positive_case(N,A) 
neg = calc_positive_case(N,A[::-1])[::-1] 

pos = [2*x for x in pos] + [0]
neg = [0] + [2*x+i for i,x in enumerate(neg,1)] 

answer = min(x+y for x,y in zip(pos,neg))
print(answer)

Solution (Python):
from math import log,ceil
N=int(input())
A=list(map(int,input().split()))
inf=float("inf")
p=[0]*(N+1)
n=[0]*(N+1)
Stack_p=[(-inf,N-1)]
Stack_n=[(-inf,0)]
for i in range(N-1)[::-1]:
  k=ceil(log(A[i]/A[i+1],4))
  p[i]=p[i+1]
  t=i
  if k>=1:
    while k>0:
      
      s,m=Stack_p.pop()
      p[i]+=k*(m-t)
      if k+s>=0:
        k+=s
        t=m
      else:
        Stack_p.append((k+s,m))   
        k=0
  elif k<0:
    Stack_p.append((k,i))
for i in range(2,N+1):
  k=ceil(log(A[i-1]/A[i-2],4))
  n[i]=n[i-1]
  t=i-1
  if k>=1:
    while k>0:
     
      s,m=Stack_n.pop()
     
      n[i]+=k*(t-m)
      t=m
      if k+s>=0:
        k+=s
      elif k+s<0:
        Stack_n.append((k+s,m))  
        k=0
     
  elif k<0:
    Stack_n.append((k,i-1))


ans=inf
for i in range(N+1):
  ans=min(ans,i+2*n[i]+2*p[i])
print(ans)

Solution (Python):
from math import ceil,log
N=int(input())
A=[int(i) for i in input().split()]
def f(A):
    dp=[0]*16
    L=[0]*N
    for i in range(16):
        dp[i]=i
    for n in range(N-2,-1,-1):
        ndp=[0]*16
        nx=ceil(log(A[n]/A[n+1])/log(4)) 
        for x in range(16):
            dx=nx+x
            if dx <=15:
                
                ndp[x]=dp[max(0,dx)]+x
            else:
                ndp[x]=dp[15]+x+(N-1-n)*(dx-15)
        dp=ndp
        L[n]=dp[0]
    return L

K=f(A)+[0]
L=[0]+f(A[::-1])[::-1]
ans=10**22
for i in range(N+1):
    ans=min(ans,i+2*L[i]+2*K[i])
print(ans)

Solution (Python):

import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    
    import numpy
    def dprint(*args, **kwargs):
        
        
        print(*args,  file=sys.stderr)
    dprint('debug mode')
except Exception:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    sys.stdin = open('input'+ str(inId) + '.txt', 'r') 
if outId>0:
    dprint('use output', outId)
    sys.stdout = open('stdout'+ str(outId) + '.txt', 'w') 
    atexit.register(lambda :sys.stdout.close())     


if True:
    N, = getIntList()
    
    za = getIntList()
else:
    N = 100
    import random
    za = [random.randint(1, 1000000000) for i in range(N) ]

dprint('begin')

zleft = [0 for i in range(N+1)]
zright = [0 for i in range(N+1)]


def getwork(zr, za):
    zr[0] = 0
    st = []
    for i in range(N):
        if i%10000  ==0:
            dprint('---', i)
        nt = [[za[i],0], [za[i],0], 1]
        st.append(nt)
        nr = zr[i]
        
        while len(st)>1:
            b_2 = st[-2][1][1]
            b_1 = st[-1][0][1]
            bb = min(b_1,b_2)
            b_1 -=bb
            b_2 -=bb
            b_1p = 4 ** b_1
            b_2p = 4 ** b_2
            t2 = st[-2][1][0] * b_2p
            t1 = st[-1][0][0] * b_1p
            if  t2 < t1:
                nr+= 2* st[-2][2]
                st[-2][0][1] +=1
                st[-2][1][1] +=1
            elif t2 < t1 * 4:
                ttt = [ st[-2][0], st[-1][1], st[-2][2] + st[-1][2] ]  
                st[-2] = ttt
                st.pop()
            else:
                break
        
        zr[i+1] = nr
        
        
        assert nr < 1000000000000000
    dprint(st)
getwork(zleft, za)
dprint('!!!!')
getwork(zright, za[::-1])
 



r =  zright[N]
for i in range(N+1):
    tr =  i + zleft[i] + zright[N-i]
    r = min(r,tr)

print(r)

dprint('end')

Solution (Python):

import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    
    import numpy
    def dprint(*args, **kwargs):
        
        
        print(*args,  file=sys.stderr)
    dprint('debug mode')
except Exception:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    sys.stdin = open('input'+ str(inId) + '.txt', 'r') 
if outId>0:
    dprint('use output', outId)
    sys.stdout = open('stdout'+ str(outId) + '.txt', 'w') 
    atexit.register(lambda :sys.stdout.close())     


if True:
    N, = getIntList()
    
    za = getIntList()
else:
    N = 1000
    import random
    za = [random.randint(1, 1000000000) for i in range(N) ]

dprint('begin')

zleft = [0 for i in range(N+1)]
zright = [0 for i in range(N+1)]


def getwork(zr, za):
    zr[0] = 0
    st = []
    for i in range(N):
        if i%10000  ==0:
            dprint('---', i)
        nt = [[za[i],0], [za[i],0], 1]
        st.append(nt)
        nr = zr[i]
        
        while len(st)>1:
            b_2 = st[-2][1][1]
            b_1 = st[-1][0][1]
            bb = min(b_1,b_2)
            b_1 -=bb
            b_2 -=bb
            b_1p = 4 ** b_1
            b_2p = 4 ** b_2
            t2 = st[-2][1][0] * b_2p
            t1 = st[-1][0][0] * b_1p
            if  t2 < t1:
                nr+= 2* st[-2][2]
                st[-2][0][1] +=1
                st[-2][1][1] +=1
            elif t2 < t1 * 4:
                ttt = [ st[-2][0], st[-1][1], st[-2][2] + st[-1][2] ]  
                st[-2] = ttt
                st.pop()
            else:
                break
        
        zr[i+1] = nr
        
        
        assert nr < 1000000000000000

getwork(zleft, za)
dprint('!!!!')
getwork(zright, za[::-1])
 



r =  zright[N]
for i in range(N+1):
    tr =  i + zleft[i] + zright[N-i]
    r = min(r,tr)

print(r)

dprint('end')

Solution (Python):
from math import ceil, log2

def getNums(As, N):
    dp = list(range(16))
    nums = [0] * N
    for i in reversed(range(N - 1)):
        dx = ceil( log2( As[i] / As[i+1] ) / 2 )
        if dx <= 0:
            dp0 = dp[0]
            dp = [dp0] * (-dx) + dp[:16+dx]
        else:
            dp15 = dp[15]
            k = N - 1 - i
            dp = dp[dx:] + list(range(dp15 + k, dp15 + k * dx + 1, k))
        dp = [dpx + x for x, dpx in enumerate(dp)]
        nums[i] = dp[0]
    return nums

N = int(input())
As = list(map(int, input().split()))

numPstvs = getNums(As, N)
numNgtvs = getNums(As[::-1], N)[::-1]

ans = min([2 * p + 2 * m + i for i, (p, m) in enumerate(zip(numPstvs + [0], [0] + numNgtvs))])
print(ans)

Solution (Python):
from math import ceil, log

log_2 = log(2)

def max2(x, y): return x if x >= y else y

def getNums(As, N):
    dp = list(range(16))
    nums = [0] * N
    for i in reversed(range(N - 1)):
        dx = ceil( log( As[i] / As[i+1] ) / log_2 / 2 )
        dp2 = [0] * 16
        for x in range(16):
            nx = x + dx
            if nx <= 15:
                dp2[x] = dp[max2(0, nx)] + x
            else:
                dp2[x] = dp[15] + x + (N - 1 - i) * (nx - 15)
        dp = dp2
        nums[i] = dp[0]
    return nums

N = int(input())
As = list(map(int, input().split()))

numPstvs = getNums(As, N)
numNgtvs = getNums(As[::-1], N)[::-1]

ans = float('inf')
for i, (p, m) in enumerate(zip(numPstvs + [0], [0] + numNgtvs)):
    ans = min(ans, 2 * p + 2 * m + i)
print(ans)

Solution (Python):
from math import floor, ceil, log2

def getNums(As, N):
    nums = [0] * N
    accNum = 0
    stack = [(N-1, float('inf'))]
    dNow = 0
    for i in reversed(range(N - 1)):
        if As[i] <= As[i+1]:
            dd = floor( log2( As[i+1] / As[i] ) / 2 )
            if dd > 0: stack.append((i, dNow))
            dNow -= dd
        else:
            dTgt = dNow + ceil( log2( As[i] / As[i+1] ) / 2 )
            while dNow < dTgt:
                pos, d = stack[-1]
                if dTgt > d:
                    accNum += (d - dNow) * (pos - i)
                    dNow = d
                    stack.pop()
                else:
                    accNum += (dTgt - dNow) * (pos - i)
                    if dTgt == d: stack.pop()
                    dNow = dTgt
                    break
        nums[i] = accNum
    return nums

N = int(input())
As = list(map(int, input().split()))

numPstvs = getNums(As, N)
numNgtvs = getNums(As[::-1], N)[::-1]

ans = float('inf')
for i, (p, m) in enumerate(zip(numPstvs + [0], [0] + numNgtvs)):
    ans = min(ans, 2 * p + 2 * m + i)
print(ans)

Solution (Python):
N = int(input())
*A, = map(int, input().split())
def dfs(A):
    st = []
    V = [0]*(N+1)
    cur = 0
    for i, a in enumerate(A):
        b = a
        p = 1
        while st and st[-1][0] < b:
            c, d, cnt = st.pop()
            while c < b:
                cur += cnt*2
                c *= 4; d *= 4
            b = d
            p += cnt
        if st:
            st.append((a, b, p))
        else:
            st.append((a, 0, p))
        V[i+1] = cur
    return V
P = dfs(A)
A.reverse()
Q = dfs(A)
ans = 10**18
for i in range(N+1):
    ans = min((P[i] + i) + Q[-1-i], ans)
print(ans)

Solution (Python):
def f(A, s):
    X = [0] * N
    q = []
    a = 0
    for i in range(N):
        b = a
        X[i] = X[i-1]
        a = A[i]
        if a * s < 0:
            X[i] += 1
            a *= -2

        if i == 0:
            continue
            
        r = b/a
        while r >= 4:
            q.append(i)
            r /= 4

        while r < 1:
            X[i] += 2 * (i - (0 if len(q) == 0 else q.pop()))
            r *= 4
            
    return X

N = int(input())
A = [int(a) for a in input().split()]
X = f(A,-1)
Y = f(A[::-1],1)

mi = min(X[-1], Y[-1])
for i in range(N-1):
    mi = min(mi, X[i] + Y[-2-i])
print(mi)

Solution (Python):
from sys import stdin
from itertools import repeat
def f(a):
    n = len(a)
    l = [0] * (n + 1)
    st = [(0, 0, 0, 1)]
    pu = st.append
    po = st.pop
    for i in xrange(1, n):
        ad = 0
        r = i
        u = 0
        k = 1
        while st and (a[r] << u) > a[st[-1][0]]:
            y = a[r] << u
            x, r, u, q = po()
            c = (((y - 1) / a[x]).bit_length() + 1) / 2 * 2
            ad += c * q
            k += q
            u += c
        pu((i, r, u, k))
        l[i+1] = l[i] + ad
    return l
 
def main():
    n = int(stdin.readline())
    a = map(int, stdin.readline().split(), repeat(10, n))
    l = f(a)
    r = f(a[::-1])[::-1]
    ans = 10 ** 12
    for i in xrange(n + 1):
        if ans > l[i] + i + r[i]:
            ans = l[i] + i + r[i]
    print ans
main()

Solution (Python):
from sys import stdin
from itertools import repeat
def f(a):
    n = len(a)
    l = [0] * (n + 1)
    st = [(0, 0, 0, 1)]
    pu = st.append
    po = st.pop
    for i in xrange(1, n):
        ad = 0
        r = i
        u = 0
        k = 1
        while st:
            y = a[r] << u
            x = a[st[-1][0]]
            if x >= y:
                break
            _, r, u, q = po()
            c = 0
            while x < y:
                x *= 4
                c += 2
            ad += c * q
            k += q
            u += c
        pu((i, r, u, k))
        l[i+1] = l[i] + ad
    return l
 
def main():
    n = int(stdin.readline())
    a = map(int, stdin.readline().split(), repeat(10, n))
    l = f(a)
    r = f(a[::-1])[::-1]
    ans = 10 ** 12
    for i in xrange(n + 1):
        if ans > l[i] + i + r[i]:
            ans = l[i] + i + r[i]
    print ans
main()

Solution (Python):
from sys import stdin
from itertools import repeat
def f(a):
    n = len(a)
    l = [0] * (n + 1)
    st = [(a[0], a[0], 1)]
    pu = st.append
    po = st.pop
    for i in xrange(1, n):
        ad = 0
        y = a[i]
        k = 1
        while st and y > st[-1][0]:
            x, z, q = po()
            c = (((y - 1) / x).bit_length() + 1) / 2 * 2
            ad += c * q
            k += q
            y = z << c
        pu((a[i], y, k))
        l[i+1] = l[i] + ad
    return l
 
def main():
    n = int(stdin.readline())
    a = map(int, stdin.readline().split(), repeat(10, n))
    l = f(a)
    r = f(a[::-1])[::-1]
    ans = 10 ** 12
    for i in xrange(n + 1):
        if ans > l[i] + i + r[i]:
            ans = l[i] + i + r[i]
    print ans
main()

Solution (Python):
from sys import stdin
from itertools import repeat
def f(a):
    n = len(a)
    l = [0] * (n + 1)
    st = [(a[0], a[0], 1)]
    pu = st.append
    po = st.pop
    for i in xrange(1, n):
        ad = 0
        y = a[i]
        k = 1
        while st and y > st[-1][0]:
            x, z, q = po()
            c = 0
            while x < y:
                x *= 4
                c += 2
            ad += c * q
            k += q
            y = z << c
        pu((a[i], y, k))
        l[i+1] = l[i] + ad
    return l

def main():
    n = int(stdin.readline())
    a = map(int, stdin.readline().split(), repeat(10, n))
    l = f(a)
    r = f(a[::-1])[::-1]
    ans = 10 ** 12
    for i in xrange(n + 1):
        if ans > l[i] + i + r[i]:
            ans = l[i] + i + r[i]
    print ans
main()

Solution (Python):
from collections import deque
 
q = deque([]) 

def ct(a,b):
    ans = 0
    while abs(a)<abs(b):
        ans += 2
        a *= 4
    return ans

N = int(input())
A = [int(a) for a in input().split()]





X = [0] * (N)
Y = [0] * (N)

a = -1
for i in range(N):
    b = a
    if i > 0:
        X[i] = X[i-1]
    else:
        X[i] = 0
    a = A[i]
    t = 0
    if a > 0:
        X[i] += 1
        a *= -2
    
    if i > 0:
        t = 0
        r = b/a
        while r >= 4:
            q.append(i)
            r /= 4
            
        while abs(a)>abs(b):
            if len(q) == 0:
                X[i] += 2 * i
            else:
                X[i] += 2 * (i - q.pop())
            b *= 4
    
q = deque([]) 
a = -1
for i in range(N):
    b = a
    if i > 0:
        Y[i] = Y[i-1]
    else:
        Y[i] = 0
    a = A[N-1-i]
    t = 0
    if a < 0:
        Y[i] += 1
        a *= -2
    
    if i > 0:
        t = 0
        r = b/a
        while r >= 4:
            q.append(i)
            r /= 4
            
        while abs(a)>abs(b):
            if len(q) == 0:
                Y[i] += 2 * i
            else:
                Y[i] += 2 * (i - q.pop())
            b *= 4

mi = min(X[-1], Y[-1])
for i in range(N-1):
    if X[i]+Y[-2-i] < mi:
        mi = X[i]+Y[-2-i]
print(mi)