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



Sample input:
4
3 1 4 1


Sample output:
3

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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
    # ある場所を始点として、そこから全部positiveにしたい場合
    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:
                # mergeせず
                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) # ある点を正の始点としたときに必要な、4倍の回数
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)] # -2倍の初期コストが乗る

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

Submission status: Accepted

Solution code:
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:
      #print(Stack_p,k,t,p)
      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:
     # print(Stack_n,k,t,n)
      s,m=Stack_n.pop()
     # print(s,m)
      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
     # print(Stack_n)
  elif k<0:
    Stack_n.append((k,i-1))
#print(p)
#print(n)
ans=inf
for i in range(N+1):
  ans=min(ans,i+2*n[i]+2*p[i])
print(ans)

Submission status: Accepted

Solution code:
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)) #A
        for x in range(16):
            dx=nx+x
            if dx <=15:
                #print(max(0,dx))
                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)

Submission status: Accepted

Solution code:
#      
import collections, atexit, math, sys, bisect 

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

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        #print(*args, **kwargs, file=sys.stderr)
        # in python 3.4 **kwargs is invalid???
        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())     #idle 中不会执行 atexit


if True:
    N, = getIntList()
    #print(N)
    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]
        #dprint(st)
        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
        #dprint(st)
        zr[i+1] = nr
        #dprint(nr)
        #dprint(st)
        assert nr < 1000000000000000
    dprint(st)
getwork(zleft, za)
dprint('!!!!')
getwork(zright, za[::-1])
 
#dprint(zleft)
#dprint(zright)

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

print(r)

dprint('end')

Submission status: Accepted

Solution code:
#      
import collections, atexit, math, sys, bisect 

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

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        #print(*args, **kwargs, file=sys.stderr)
        # in python 3.4 **kwargs is invalid???
        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())     #idle 中不会执行 atexit


if True:
    N, = getIntList()
    #print(N)
    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]
        #dprint(st)
        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
        #dprint(st)
        zr[i+1] = nr
        #dprint(nr)
        #dprint(st)
        assert nr < 1000000000000000

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

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

print(r)

dprint('end')

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()]

# A = [3, 1, 4, 1]
# N = len(A)


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)

Submission status: Accepted

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

R = [0] * (N+1)
L = [0] * (N+1)
l = 0
ap = A[-1]#float("inf")
P = [0] * 20
stack = [0]

for i in range(N):
    a = A[-1-i]
    #cnt = 0
    while ap < a:
        #cnt += 2
        l += (i-stack[-1])<<1
        if stack[-1] != 0: del stack[-1]
        ap <<= 2
    a4 = a<<2
    while ap >= a4:
        ap >>= 2
        stack.append(i)
    R[-(i+2)] = l
    ap = a
ap = -A[0]
l = 0
stack = [0]
for i in range(N):
    l += 1
    a = -A[i]
    #cnt = 0

    while ap > a:
        #cnt += 2
        l += (i-stack[-1])<<1
        if stack[-1] != 0: del stack[-1]
        ap <<= 2
    a4 = a << 2
    while ap <= a4:
        ap >>= 2
        stack.append(i)
    #l += i * cnt
    L[i+1] = l
    ap = a
#print(L, R)
ans = float("inf")
for l, r in zip(L, R):
    ans = min(ans, l+r)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

if(n==1):
    print(0)
    exit()

all_plus = [0] * n
all_minus = [0] * n

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

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

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

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

ans = min(cumsum_p[0], cumsum_m[-1])
for i in range(1,n):
    #minusの数がi個あるとする。
    tmp = cumsum_m[i] + cumsum_p[i]
    ans = min(ans,tmp)

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

if(n==1):
    print(0)
    exit()

all_plus = [0] * n
all_minus = [0] * n

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

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

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

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

ans = min(cumsum_p[0], cumsum_m[-1])
for i in range(1,n):
    #minusの数がi個あるとする。
    tmp = cumsum_m[i] + cumsum_p[i]
    ans = min(ans,tmp)

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np


def calc_mul4_dp(n, aaa):
    # dp[i] = aaa[i] 以右をascendingにするために4をかける必要のある回数

    # 「支配的」である数と位置を記録するstack
    # 支配的: それを4倍すると、それより右で次に支配的な数までは全て4倍する必要のある数
    # (支配的な数, ←をいじらなかった場合の支配区間の最後の数, 最初の数の位置)
    stack = [(10 ** 20, 10 ** 20, n), (aaa[-1], aaa[-1], n - 1)]
    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 = e << (2 * mul)
        stack.append((a, c, i))
        result.append(inc)
        # print(a, stack, result)
    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]
    # print(fdp)
    # print(bdp)
    return ((fdp + bdp) * 2 + np.arange(n + 1, dtype=np.int64)).min()


def test():
    import random
    n = 200000
    # aaa = random.choices(range(1, 10 ** 9), k=n)
    # aaa = [1, 10 ** 9] * (n // 2)
    aaa = list(range(10 ** 9, 10 ** 9 - n, -1))
    print(n)
    # print(aaa)
    print(solve(n, aaa))


# test()

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

Submission status: Runtime Error

Solution code:
import math
n = int(input())
a = list(map(int, input().split()))

# [0,border)が負になり、[border,n)が正になるときの操作の回数
def multi_times(border):
    ans = 0
    num = 1
    for i in range(border, n):
        if num <= a[i]:
            num = a[i]
        else:
            cnt = int(math.log2(num/a[i])/2 + 0.99999)
            num = (4**cnt) * a[i]
            ans += cnt * 2

    num = 1
    for i in range(0, border)[::-1]:
        ans += 1
        if num <= a[i]:
            num = a[i]
        else:
            cnt = int(math.log2(num/a[i])/2 + 0.99999)
            num = (4**cnt) * a[i]
            ans += cnt * 2
    return ans
s = float("inf")
for i in range(n+1):
    s = min(s, multi_times(i))
print(s)

Submission status: Runtime Error

Solution code:
import math
n = int(input())
a = list(map(int, input().split()))

# [0,border)が負になり、[border,n)が正になるときの操作の回数
def multi_times(border):
    ans = 0
    num = 1
    for i in range(border, n):
        if num <= a[i]:
            num = a[i]
        else:
            cnt = int(math.log2(num/a[i])/2 + 0.99999)
            num = (4**cnt) * cnt * a[i]
            ans += cnt * 2

    num = 1
    for i in range(0, border)[::-1]:
        ans += 1
        if num <= a[i]:
            num = a[i]
        else:
            cnt = int(math.log2(num/a[i])/2 + 0.99999)
            num = (4**cnt) * a[i]
            ans += cnt * 2
    return ans
s = float("inf")
for i in range(n+1):
    s = min(s, multi_times(i))
print(s)

Submission status: Runtime Error

Solution code:
import math
n = int(input())
a = list(map(int, input().split()))

# [0,border)が負になり、[border,n)が正になるときの操作の回数
def multi_times(border):
    ans = 0
    num = 1
    for i in range(border, n):
        if num <= a[i]:
            num = a[i]
        else:
            cnt = int(math.log2(num/a[i])/2 + 0.99999)
            num = (4**cnt) * cnt * a[i]
            ans += cnt * 2

    num = 1
    for i in range(0, border)[::-1]:
        ans += 1
        if num <= a[i]:
            num = a[i]
        else:
            cnt = int(math.log2(num/a[i])/2 + 0.99999)
            num = (4**cnt) * a[i]
            ans += cnt * 2
    return ans

ok = n+1
ng = 0

while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if mid == 0 or mid == n:
        print(multi_times(mid))
        exit()
    l = multi_times(mid-1)
    m = multi_times(mid)
    r = multi_times(mid+1)
    if l <= m <= r:
        ok = mid
    elif l >= m >= r:
        ng = mid
    else:
        print(min(l,m,r))
        exit()
mid = (ok+ng)//2
print(min(multi_times(mid),multi_times(max(0, mid-1)),multi_times(min(n, mid+1))))

Submission status: Runtime Error

Solution code:
import math
n = int(input())
a = list(map(int, input().split()))

# [0,border)が負になり、[border,n)が正になるときの操作の回数
def multi_times(border):
    ans = 0
    num = 1
    for i in range(border, n):
        if num <= a[i]:
            num = a[i]
        else:
            cnt = int(math.log2(num/a[i])/2 + 0.99999)
            num = (4**cnt) * cnt * a[i]
            ans += cnt * 2

    num = 1
    for i in range(0, border)[::-1]:
        ans += 1
        if num <= a[i]:
            num = a[i]
        else:
            cnt = int(math.log2(num/a[i])/2 + 0.99999)
            num = (4**cnt) * a[i]
            ans += cnt * 2
    return ans

ok = n+1
ng = 0

while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if mid == 0 or mid == n:
        print(multi_times(mid))
        break
    if multi_times(mid-1) < multi_times(mid+1):
        ok = mid
    else:
        ng = mid
else:
    print(min(multi_times(mid),multi_times(max(0, mid-1)),multi_times(min(n, mid+1))))

Submission status: Runtime Error

Solution code:
import math
n = int(input())
a = list(map(int, input().split()))

# [0,border)が負になり、[border,n)が正になるときの操作の回数
def multi_times(border):
    ans = 0
    num = 1
    for i in range(border, n):
        if num <= a[i]:
            num = a[i]
        else:
            cnt = int(math.log2(num/a[i])/2 + 0.99999)
            num = (4**cnt) * cnt * a[i]
            ans += cnt * 2

    num = 1
    for i in range(0, border)[::-1]:
        ans += 1
        if num <= a[i]:
            num = a[i]
        else:
            cnt = int(math.log2(num/a[i])/2 + 0.99999)
            num = (4**cnt) * a[i]
            ans += cnt * 2
    return ans

ok = n+1
ng = 0

while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if mid == 0 or mid == n:
        print(multi_times(mid))
        break
    if multi_times(mid-1) < multi_times(mid+1):
        ok = mid
    else:
        ng = mid
else:
    print(min(multi_times(mid),multi_times(mid-1),multi_times(mid+1)))