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: Wrong Answer

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 = 200000
    za = [1 for i in range(N) ]

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], za[i], 1, 0, 0]
        st.append(nt)
        nr = zr[i]
        #dprint(st)
        while len(st)>1:
            b_2 = st[-2][4]
            b_1 = st[-1][3]
            bb = min(b_1,b_2)
            b_1 -=bb
            b_2 -=bb
            b_1p = 4 ** b_1
            b_2p = 4 ** b_2
            if st[-2][1] * b_2p < st[-1][0] * b_1p:
                nr+= 2* st[-2][2]
                st[-2][3] +=1
                st[-2][4] +=1
            elif st[-2][1]* b_2p < st[-1][0] * b_1p *4:
                ttt = [ st[-2][0], st[-1][1], st[-2][2] + st[-2][2],
                        st[-2][3], st[-1][4] ]
                st[-2] = ttt
                st.pop()
            else:
                break
        #dprint(st)
        zr[i+1] = nr


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)

Submission status: Wrong Answer

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

flag = True
r = 0
for i in range(n-1):
  if a[i] > a[i+1]:
    if flag:
      a[i] *= -2
      r += 1
    else:
      while a[i] > a[i+1]:
        a[i+1] *= 4
        r += 2
  else:
    flag = False

print(r)

Submission status: Wrong Answer

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

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

count = 0
if a[0] > a[1]:
    count += 1

for i in range(1, n-1):
    while a[i] > a[i+1]:
        count += 2
        a[i+1] *= 4
print(count)

Submission status: Wrong Answer

Solution code:
import collections
import math


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

    lft = 0
    rgt = n
    while rgt - lft > 2:
        mi1 = (lft * 2 + rgt) // 3
        mi2 = (lft + rgt * 2) // 3
        ret1 = eval(a, mi1)
        ret2 = eval(a, mi2)
        if ret1 < ret2:
            rgt = mi2
        else:
            lft = mi1

    hoge = [eval(a, i) for i in range(lft, min([lft + 3, n]))]
    # hoge = [eval(a, i) for i in range(n)]
    print(min(hoge) if hoge else eval(a, n - 1))

def eval(a, m):
    ret = m
    if m > 0:
        tmp = a[m - 1]
        for i in range(m - 1, 0, -1):
            if a[i - 1] < tmp:
                cnt = math.ceil(math.log(tmp / a[i - 1], 4))
                ret += cnt * 2
                tmp = a[i - 1] * 4 ** cnt
            else:
                tmp = a[i - 1]
            if tmp > 1e100:
                return -1
    tmp = a[m]
    for i in range(m + 1, len(a)):
        if a[i] < tmp:
            cnt = math.ceil(math.log(tmp / a[i], 4))
            if cnt < -1:
                return -1
            ret += cnt * 2
            tmp = a[i] * 4 ** cnt
        else:
            tmp = a[i]
        if tmp > 1e100:
            return -1
    return ret


main()

Submission status: Wrong Answer

Solution code:
import sys
import copy
import math
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))
A=[math.log(A[i],4) for i in range(N)]

#負にする個数で場合分け

MIN=0
MAX=N-1
#何個負にするかで二分探索

while True:
    j=(MAX+MIN)//2
    l=min(j+1,N-1)

    ANSj=j
    AR=copy.copy(A)
    for i in range(j+1,N):
        if AR[i]<AR[i-1]:
            x=math.ceil(AR[i-1]-AR[i])
            AR[i]+=x
            ANSj+=2*x

    for i in range(j-2,-1,-1):
        if AR[i]<AR[i+1]:
            x=math.ceil(AR[i+1]-AR[i])
            AR[i]+=x
            ANSj+=2*x

    ANSl=l
    AR=copy.copy(A)
    for i in range(l+1,N):
        if AR[i]<AR[i-1]:
            x=math.ceil(AR[i-1]-AR[i])
            AR[i]+=x
            ANSl+=2*x

    for i in range(j-2,-1,-1):
        if AR[i]<AR[i+1]:
            x=math.ceil(AR[i+1]-AR[i])
            AR[i]+=x
            ANSl+=2*x

    if MAX-MIN<=1:
        print(min(ANSj,ANSl))
        break

    if ANSj<=ANSl:
        MAX=j
    else:
        MIN=l

Submission status: Wrong Answer

Solution code:
import math
import functools

N = int(input())
A = list(map(int,input().split()))
N_I = [0 for _ in range(N-1)]
N_D = [1 for _ in range(N-1)]

for i in range(1,N):
    if A[i-1] > A[i]:
        N_I[i-1] += math.ceil(math.log(A[i-1]/A[i],4)) *2*  (N-i)
    if A[i-1] < A[i]:
        N_D[i-1] += math.ceil(math.log(A[i]/A[i-1],4)) *2*  i


# print(N_I)
# print(N_D)

N_I_SUM = []
N_D_SUM = [0]
_sum =0
for x in reversed(N_I):
    _sum +=x
    N_I_SUM.append(_sum)

N_I_SUM.reverse()
N_I_SUM.append(0)
_sum =0
for x in N_D:
    _sum+=x
    N_D_SUM.append(_sum)
#
# print(N_I_SUM)
# print(N_D_SUM)

print(min(N_D_SUM[i]+N_I_SUM[i] for i in range(N)))

Submission status: Wrong Answer

Solution code:
from math import log, ceil

EPS = 1e-6


def _check(bbb):
    ret = 0
    pb = -1
    for b in bbb:
        if pb > b:
            d = ceil((pb - b) / 2 - EPS) * 2
            ret += d
            b += d
        pb = b
    return ret


def check(x, bbb):
    ret = x
    ret += _check(bbb[x:])
    ret += _check(reversed(bbb[:x]))
    return ret


def solve(n, aaa):
    l = 0
    r = n
    bbb = [log(a, 2) for a in aaa]
    while l < r:
        m1 = (l + r) // 2
        m2 = m1 + 1
        res1 = check(m1, bbb)
        res2 = check(m2, bbb)
        # print(l, r, m1, m2, res1, res2)
        if res1 > res2:
            l = m1 + 1
        else:
            r = m1
    return check(r, bbb)


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

Submission status: Wrong Answer

Solution code:
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 = ct(b,a)
    
    X[i] += i * t
    
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 = ct(b,a)
    
    Y[i] += i * t
# print(i, N, A, X, Y, t, a, b)

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(i, X[i], Y[-2-i])
print(mi)

Submission status: Wrong Answer

Solution code:
import sys
import copy
import math
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))
A=[math.log(A[i],4) for i in range(N)]

#負にする個数で場合分け

MIN=0
MAX=N-1
#何個負にするかで二分探索

while True:
    j=(MAX+MIN)//2
    l=min(j+1,N-1)

    ANSj=j
    AR=copy.copy(A)
    for i in range(j+1,N):
        if AR[i]<AR[i-1]:
            x=math.ceil(AR[i-1]-AR[i])
            AR[i]+=x
            ANSj+=2*x

    for i in range(j-2,-1,-1):
        if AR[i]<AR[i+1]:
            x=math.ceil(AR[i+1]-AR[i])
            AR[i]+=x
            ANSj+=2*x

    ANSl=l
    AR=copy.copy(A)
    for i in range(l+1,N):
        if AR[i]<AR[i-1]:
            x=math.ceil(AR[i-1]-AR[i])
            AR[i]+=x
            ANSl+=2*x

    for i in range(j-2,-1,-1):
        if AR[i]<AR[i+1]:
            x=math.ceil(AR[i+1]-AR[i])
            AR[i]+=x
            ANSl+=2*x

    if MAX-MIN==1:
        print(min(ANSj,ANSl))
        break

    if ANSj<=ANSl:
        MAX=j
    else:
        MIN=l

Submission status: Wrong Answer

Solution code:
from math import log, ceil


def _check(bbb):
    ret = 0
    pb = -1
    for b in bbb:
        if pb > b:
            d = ceil((pb - b) / 2) * 2
            ret += d
            b += d
        pb = b
    return ret


def check(x, bbb):
    ret = x
    ret += _check(bbb[x:])
    ret += _check(reversed(bbb[:x]))
    return ret


def solve(n, aaa):
    l = 0
    r = n
    bbb = [log(a, 2) for a in aaa]
    while l < r:
        m1 = (l + r) // 2
        m2 = m1 + 1
        res1 = check(m1, bbb)
        res2 = check(m2, bbb)
        # print(l, r, m1, m2, res1, res2)
        if res1 > res2:
            l = m1 + 1
        else:
            r = m1
    return check(r, bbb)


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

Submission status: Wrong Answer

Solution code:
import sys
import copy
import math
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))
A=[math.log(A[i],4) for i in range(N)]

#負にする個数で場合分け

MIN=0
MAX=N-1
#何個負にするかで二分探索

while True:
    j=(MAX+MIN)//2
    k=max(0,j-1)
    l=min(j+1,N-1)

    ANSj=j
    AR=copy.copy(A)
    for i in range(j+1,N):
        if AR[i]<AR[i-1]:
            x=math.ceil(AR[i-1]-AR[i])
            AR[i]+=x
            ANSj+=2*x

    for i in range(j-2,-1,-1):
        if AR[i]<AR[i+1]:
            x=math.ceil(AR[i+1]-AR[i])
            AR[i]+=x
            ANSj+=2*x

    ANSk=k
    AR=copy.copy(A)
    for i in range(k+1,N):
        if AR[i]<AR[i-1]:
            x=math.ceil(AR[i-1]-AR[i])
            AR[i]+=x
            ANSk+=2*x

    for i in range(k-2,-1,-1):
        if AR[i]<AR[i+1]:
            x=math.ceil(AR[i+1]-AR[i])
            AR[i]+=x
            ANSk+=2*x

    ANSl=j
    AR=copy.copy(A)
    for i in range(l+1,N):
        if AR[i]<AR[i-1]:
            x=math.ceil(AR[i-1]-AR[i])
            AR[i]+=x
            ANSl+=2*x

    for i in range(j-2,-1,-1):
        if AR[i]<AR[i+1]:
            x=math.ceil(AR[i+1]-AR[i])
            AR[i]+=x
            ANSl+=2*x

    if ANSj<=ANSk and ANSj<=ANSl:
        print(ANSj)
        break

    if j==0 and ANSj<=ANSl:
        print(ANSj)
        break

    if j==N-1 and ANSj<=ANSk:
        print(ANSj)
        break

    if ANSj>ANSk:
        MAX=j-1
    if ANSj>ANSl:
        MIN=j+1

Submission status: Wrong Answer

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
    
N, = getIntList()
#print(N)
za = getIntList()

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):
        nt = [za[i], za[i], 1, 0, 0]
        st.append(nt)
        nr = zr[i]
        dprint(st)
        while len(st)>1:
            b_2 = st[-2][4]
            b_1 = st[-1][3]
            bb = min(b_1,b_2)
            b_1 -=bb
            b_2 -=bb
            b_1p = 4 ** b_1
            b_2p = 4 ** b_2
            if st[-2][1] * b_2p < st[-1][0] * b_1p:
                nr+= 2* st[-2][2]
                st[-2][3] +=1
                st[-2][4] +=1
            elif st[-2][1]* b_2p < st[-1][0] * b_1p *4:
                ttt = [ st[-2][0], st[-1][1], st[-2][2] + st[-2][2],
                        st[-2][3], st[-1][4] ]
                st[-2] = ttt
                st.pop()
            else:
                break
        dprint(st)
        zr[i+1] = nr


getwork(zleft, za)
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)

Submission status: Wrong Answer

Solution code:
import math
import functools

def nibun(func, min_, max_):
    left = min_
    right = max_
    while not (left == right):
        mid = (left + right) // 2
        tmp = func(mid)
        if tmp:
            right = mid
        else:
            left = mid + 1
    return left

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

@functools.lru_cache()
def solve(i=0):
    # i番目以前は-2倍
    ans = i
    last_val = A[i]
    ans += solve_a(A[i],A[i+1:])
    if i>=2:
        ans += solve_a(A[i-1],reversed(A[:i-2]))
    return ans

def solve_a(start_val,A_list):
    tmp_ans = 0
    last_val = math.log(start_val,4)
    for index, x in enumerate(A_list):
        # n = 0
        # while x * (4 ** n) < last_val:
        #     n += 1
        # log x + n log 4 < log last_val
        # n < log last_val/x / log 4
        n=0
        xlog = math.log(x,4)
        if xlog < last_val:
            n  = math.ceil(last_val -xlog)
            tmp_ans += 2 * n
        last_val = xlog+  n
    return tmp_ans
def f(x):
    return solve(x+1) > solve(x)
print(solve(nibun(f,0,N-1)))

Submission status: Wrong Answer

Solution code:
import sys
import copy
import math
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))
A=[math.log(A[i],4) for i in range(N)]

#負にする個数で場合分け
ANS=float("inf")

for j in range(min(N,45)):

    ANSj=j
    AR=copy.copy(A)
    for i in range(j+1,N):
        if AR[i]<AR[i-1]:
            x=math.ceil(AR[i-1]-AR[i])
            AR[i]+=x
            ANSj+=2*x

    for i in range(j-2,-1,-1):
        if AR[i]<AR[i+1]:
            x=math.ceil(AR[i+1]-AR[i])
            AR[i]+=x
            ANSj+=2*x

    if ANS>ANSj:
        ANS=ANSj

    #print(AR,ANSj)

print(ANS)

Submission status: Wrong Answer

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
    
N, = getIntList()
#print(N)
za = getIntList()

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):
        nt = [za[i], za[i], 1, 0]
        st.append(nt)
        nr = zr[i]
        dprint(st)
        while len(st)>1:
            b_2 = st[-2][3]
            b_1 = st[-1][3]
            bb = min(b_1,b_2)
            b_1 -=bb
            b_2 -=bb
            b_1p = 4 ** b_1
            b_2p = 4 ** b_2
            if st[-2][1] * b_2p < st[-1][0] * b_1p:
                nr+= 2* st[-2][2]
                st[-2][3] +=1
            elif st[-2][1]* b_2p < st[-1][0] * b_1p *4:
                ttt = [ st[-2][0], st[-1][1], st[-2][2] + st[-2][2], bb]
                ttt[0] *= b_2p
                ttt[1] *= b_1p

                st[-2] = ttt
                st.pop()
            else:
                break
        dprint(st)
        zr[i+1] = nr


getwork(zleft, za)
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)

Submission status: Wrong Answer

Solution code:
def _check(bbb):
    ret = 0
    pa = -1
    cnt = 0
    for a in bbb:
        while pa > a:
            pa >>= 2
            cnt += 2
            ret += cnt
        pa = a
    return ret


def check(x, aaa):
    ret = x
    ret += _check(aaa[x:])
    ret += _check(reversed(aaa[:x]))
    return ret


def solve(n, aaa):
    l = 0
    r = n
    while l < r:
        m1 = (l + r) // 2
        m2 = m1 + 1
        res1 = check(m1, aaa)
        res2 = check(m2, aaa)
        # print(l, r, m1, m2, res1, res2)
        if res1 > res2:
            l = m1 + 1
        else:
            r = m1
    return check(r, aaa)


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

Submission status: Wrong Answer

Solution code:
import math
def nibun(func, min_, max_):
    left = min_
    right = max_
    while not (left == right):
        mid = (left + right) // 2
        tmp = func(mid)
        if tmp:
            right = mid
        else:
            left = mid + 1
    return left

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

def solve(i=0):
    # i番目以前は-2倍
    ans = i
    last_val = A[i]
    ans += solve_a(A[i],A[i+1:])
    if i>=2:
        ans += solve_a(A[i-1],reversed(A[:i-2]))
    return ans

def solve_a(start_val,A_list):
    tmp_ans = 0
    last_val = math.log(start_val,4)
    for index, x in enumerate(A_list):
        # n = 0
        # while x * (4 ** n) < last_val:
        #     n += 1
        # log x + n log 4 < log last_val
        # n < log last_val/x / log 4
        n=0
        xlog = math.log(x,4)
        if xlog < last_val:
            n  = math.ceil(last_val -xlog)
            tmp_ans += 2 * n
        last_val = xlog+  n
    return tmp_ans
def f(x):
    return solve(x+1) > solve(x)
print(solve(nibun(f,0,N-1)))

Submission status: Wrong Answer

Solution code:
import math

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 = max(-int(-math.log2(a/b)//2) * 2, 0)
    
    X[i] += i * t
    
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 = max(-int(-math.log2(a/b)//2) * 2, 0)
    
    Y[i] += i * t
# print(i, N, A, X, Y, t, a, b)

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(i, X[i], Y[-2-i])
print(mi)

Submission status: Wrong Answer

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

up = [0]
for i in range(N-1):
    if a[i+1]>=a[i]:
        up.append(0)
    else:
        counter = 0
        ll = a[i+1]
        while a[i]>=ll:
            ll*=4
            counter+=1
        up.append(counter)

dn = [0]
a.reverse()
for i in range(N-1):
    if a[i+1]>=a[i]:
        dn.append(0)
    else:
        counter = 0
        ll = a[i+1]
        while a[i]>=ll:
            ll*=4
            counter+=1
        dn.append(counter)

dn.reverse()

preans = 0
for i in range(1,N):
    preans += up[i]*(N-i)*2

ans = preans
for pos in range(1,N):
    preans-=up[pos]*(N-pos)*2
    preans += 1
    preans += dn[pos-1]*pos*2
    if ans>preans:
        ans=preans
print(ans)

Submission status: Wrong Answer

Solution code:
def do_sub(A):
    if len(A) <= 1: return 0

    N = len(A)
    res = 0
    acc = 0
    for i in range(1, N):
        if A[i-1] <= A[i]: continue
        d = (A[i-1]+A[i]-1)//A[i]
        if (d & (d-1)) != 0:
            d <<= 1

        bl = d.bit_length() // 2 * 2
        res += bl + acc
        acc += bl

    return res

def do(A, k):
    # [:k]: negative
    # [k:]: positive
    res = k
    res += do_sub([2*ai for ai in A[:k]][::-1])
    res += do_sub(A[k:])
    return res

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

    if A == sorted(A):
        print(0)
        return 0

    lb, ub = 0, N
    res = 1e308
    while ub-lb > 1:
        mid = (lb+ub) >> 1
        left = do(A, mid)
        right = do(A, mid+1)
        res = min(res, left, right)
        if left < right:
            ub = mid
        else:
            lb = mid

    print(res)
    return 0

main()

Submission status: Wrong Answer

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

x = 0
k = 0
while True:
    if k == len(a) - 1:
        break
    if a[k] <= a[k+1]:
        k+=1
    else:
        if k >= len(a)//2:
            if a[k] < 0:
                a[k+1] *= -2
                x += 1
            else:
                a[k + 1] *= 4
                x += 2
            k = 0
        else:
            if a[k] < 0:
                a[k] *= 4
                x += 2
            else:
                a[k] *= -2
                x += 1
            k = 0
#         print(a)
print(x)

Submission status: Wrong Answer

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
    
N, = getIntList()
#print(N)
za = getIntList()

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):
        nt = [za[i], za[i], 1]
        st.append(nt)
        nr = zr[i]
        
        while len(st)>1:
            if st[-2][1] < st[-1][0]:
                nr+= 2* st[-2][2]
                st[-2][0]*=4
                st[-2][1]*=4
            elif st[-2][1] < st[-1][0]*4:
                ttt = [ st[-2][0], st[-1][1], st[-2][2] + st[-2][2] ]
                st[-2] = ttt
                st.pop()
            else:
                break
        zr[i+1] = nr


getwork(zleft, za)
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)

Submission status: Wrong Answer

Solution code:
import itertools, sys
def inpl(): return [int(i) for i in input().split()]

N = int(input())
A = inpl()
if N == 1:
    print(0)
    sys.exit()
if N == 2:
    if A[0] <= A[1]:
        print(0)
    else:
        print(1)
    sys.exit()
    
rig = [0]*(N-1)
lef = [0]*(N-1)
for i in range(N-1):
    ctr = 1
    pre = A[i]
    nex = A[i+1] 
    while pre < nex:
        pre *= 4
        ctr += 2
    rig[i] = ctr
    ctr = 0
    pre = A[i]
    nex = A[i+1] 
    while nex < pre:
        nex *= 4
        ctr += 2
    lef[i] = ctr
lef.reverse()
lef = [i*v for i, v in enumerate(lef, 1)]
lef.reverse()
lef = list(itertools.accumulate(lef))
rig = [i*v for i, v in enumerate(rig, 1)]
rig = list(itertools.accumulate(rig))
ans = lef[N-2]
Su = lef[N-2]
for j in range(N-2):
    ans = min(ans, rig[j]+Su-lef[j])
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
al = list(map(int, input().split()))

res = 0
ca = al[0]
flag = True
for i in range(1,n):
    if ca>=al[i] and flag:
        res += 1
        ca = al[i]
        al[i] *= -2
    else:
        # if flag:
        #     if i>0:
        #         al[0] *= -2
        #     al[i-1] //= -2
        flag = False
        while ca>al[i]:
            al[i] *= 4
            res += 2
        ca = al[i]
# print(al)
print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

up = [0]
for i in range(N-1):
    if a[i+1]>a[i]:
        up.append(0)
    else:
        x = a[i]/a[i+1]
        up.append((np.log2(x)+0.1**10)//2+1)

dn = [0]
a.reverse()
for i in range(N-1):
    if a[i+1]>a[i]:
        dn.append(0)
    else:
        x = a[i]/a[i+1]
        dn.append((np.log2(x)+0.1**10)//2+1)

dn.reverse()

preans = 0
for i in range(1,N):
    preans += up[i]*(N-i)*2

ans = preans
for pos in range(1,N):
    preans-=up[pos]*(N-pos)*2
    preans += 1
    preans += dn[pos-1]*pos*2
    if ans>preans:
        ans=preans
print(int(ans))

Submission status: Wrong Answer

Solution code:
import math

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 = max(-int(-math.log2(a/b)//2) * 2, 0)
    
    X[i] += i * t
    # print(i, N, A, X, t, a, b)

    
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 = max(-int(-math.log2(a/b)//2) * 2, 0)
    
    Y[i] += i * t

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: Wrong Answer

Solution code:
import math
def nibun(func, min_, max_):
    left = min_
    right = max_
    while not (left == right):
        mid = (left + right) // 2
        tmp = func(mid)
        if tmp:
            right = mid
        else:
            left = mid + 1
    return left

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

def solve(i=0):
    # i番目以前は-2倍
    ans = i
    last_val = A[i]
    ans += solve_a(A[i],A[i+1:])
    if i>=2:
        ans += solve_a(A[i-1],reversed(A[:i-2]))
    return ans

def solve_a(start_val,A_list):
    tmp_ans = 0
    last_val = start_val
    for index, x in enumerate(A_list):
        if x < last_val:
            n = 0
            while x * (4 ** n) < last_val:
                n += 1
            tmp_ans += 2 * n
            last_val = x * (4** n)
        else:
            last_val = x
    return tmp_ans
def f(x):
    return solve(x+1) > solve(x)
print(solve(nibun(f,0,N-1)))

Submission status: Wrong Answer

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

R = [0] * (N+1)
L = [0] * (N+1)
l = 0
ap = float("inf")
for i in range(N):
    a = A[-1-i]
    cnt = 0
    while ap < a:
        cnt += 2
        ap *= 4
    l += i * cnt
    R[-(i+2)] = l
    ap = a
#print(R)
ap = -(float("inf"))
l = 0
for i in range(N):
    l += 1
    a = -A[i]
    cnt = 0
    while ap > a:
        cnt += 2
        ap *= 4
    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: Wrong Answer

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
    
N, = getIntList()
#print(N)
za = getIntList()

zleft = [0 for i in range(N+1)]
zright = [0 for i in range(N+1)]
zleft[0] = 0
for i in range(0,N):
    if i==0:
        c = 0
    else:
        t = za[i-1]
        c = 0
        while t < za[i]:
            t*=4
            c+=2
    zleft[i+1] =  zleft[i]  + i*c + 1
dprint(zleft)


zright[N] = 0
for i in range(N-1,-1,-1):
    if i==N-1:
        c = 0
    else:
        t = za[i+1]
        c = 0
        while t < za[i]:
            t*=4
            c+=2
 
            
    zright[i] =  zright[i+1]  + (N-1 -i) * c

dprint(zright)

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

print(r)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import repeat
def main():
    n = int(stdin.readline())
    a = map(int, stdin.readline().split(), repeat(10, n))
    r = [0] * (n + 1)
    l = [0] * (n + 1)
    for i in xrange(n - 1, 0, -1):
        x = a[i]
        c = 0
        while x < a[i-1]:
            x *= 4
            c += 2
        r[i-1] = r[i] + (n - i) * c
    l[1] = 1
    for i in xrange(1, n):
        x = a[i-1]
        c = 0
        while x < a[i]:
            x *= 4
            c += 2
        l[i+1] = l[i] + i * c + 1
    ans = 1001001001
    for i in xrange(n):
        if ans > l[i] + r[i]:
            ans = l[i] + r[i]
    print ans
main()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
B0=[i for i in A]
B1=[i for i in A]
ans0=1
B0[0]*=(-2)
for i in range(N-1):
    if B0[i]<=B0[i+1]:
        continue
    while(True):
        if B0[i]<=B0[i+1]:
            break
        B0[i+1]*=(-2)
        ans0+=1
ans1=0
for i in range(N-1):
    if B1[i]<=B1[i+1]:
        continue
    while(True):
        if B1[i]<=B1[i+1]:
            break
        B1[i+1]*=(-2)
        ans1+=1
print(min(ans0,ans1))